原题地址http://poj.org/problem?id=3914
DuLL
Time Limit:1000MS |
|
Memory Limit:65536K |
|
|
|
Description
In Windows, a DLL (or dynamic link library) is a file that contains a collection of pre-compiled functions that can be loaded into a program at runtime. The two primary benefits of DLLs
are (1) only one copy of a DLL is needed in memory, regardless of how many different programs are using it at the same time, and (2) since they are separate from programs, DLLs can be upgraded independently, without having to recompile the programs that use
them. (DLLs have their problems, too, but we’ll ignore those for now.) Your job is to calculate the maximum memory usage when running a series of programs together with the DLLs they need.
The DLLs in our system are not very exciting. These dull DLLs (or DuLLs) each require a fixed amount of memory which never changes as long as the DuLL is in memory. Similarly, each program has its own fixed memory requirements which never change as long as
the program is executing. Each program also requires certain DuLLs to be in memory the entire time the program is executing. Therefore, the only time the amount of memory required changes is when a new program is executed, or a currently running program exits.
When a new program begins execution, all DuLLs required by that program that must be loaded into memory if they are not there already. When a currently running program exits, all DuLLs that are no longer needed by any currently running programs are removed
from memory.
Remember, there will never be more than one copy of a specific DuLL in memory at any given time. However, it is possible for multiple instances of the same program to be running at the same time. In this case each instance of the program would require its own
memory; however, the instances still share DuLLs in the same way two unrelated programs would.
Input
The input consists of at least one data set, followed by a line containing only 0.
The first line of a data set contains three space separated integers N P S, where N is the number of DuLLs available, 1 ≤ N ≤ 20, P is the number of programs which can be executed, 1 ≤ P ≤ 9, and S is the number of state transitions recorded, 1 ≤ S ≤ 32.
The next line contains exactly N space separated integers representing the sizes in bytes of each of the DuLLs, 1 ≤ size ≤ 1,000. Each DuLL is implicitly labeled with a letter: ‘A’, ‘B’, ‘C’, ..., possibly extending to ‘T’. Therefore the first integer is the
size of ‘A’, the second integer is the size of ‘B’, and so on.
The next P lines contain information about each of the programs, one program per line. Each line contains a single integer representing the size of the program in bytes, 1 ≤ size ≤ 1,000, followed by 1 to N characters representing the DuLLs required by that
program. There will be a single space between the size of the program and the DuLL labels, but no spaces between the labels themselves. The order of the labels is insignificant and therefore undefined, but they will all be valid DuLL labels, and no label will
occur more than once. Each program is implicitly labeled with an integer: 1, 2, 3, ... possibly extending to 9.
The final line of the data set will contain S space separated integers. Each integer will either be a positive number q, 1 ≤ q ≤ P, indicating that a new execution of program q has begun, or else it will be a negative number –q, 1 ≤ q ≤ P, indicating that a
single execution of program q has completed. The transitions are given in the order they occurred. Each is a valid program number; if it is a negative number –q then there will always be at least one instance of program q running.
Output
There is one line of output for each data set, containing only the maximum amount of memory required throughout the execution of the data set.
Sample Input
5 4 8
100 400 200 500 300
250 AC
360 ACE
120 AB
40 DE
2 3 4 -3 1 2 -2 1
0
Sample Output
1600
2110
分享到:
相关推荐
poj 3914 DuLL.md
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
北大POJ初级-图算法 解题报告+AC代码
poj2009离线题库 poj2009离线题库
北大POJ初级-基本算法 解题报告+AC代码
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
用贪心算法解决POJ 1065的木棍处理问题
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
关于C++ 算法 北大网站POJ 八数码问题
北大POJ初级-动态规划 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
PKU Online Judge上面很全面的...动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,学长给的,在此分享
包含15类的POJ推荐50题,可全面复习或学习算法。 除此外还包含三种级别的水平(初级、中级、高级)应掌握的算法及数据结构及... (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
poj1087贪心算法实验报告 poj1087贪心算法实验报告