POJ 1036
时间：2010-10-06 来源：wbh23
Gangsters
The restaurant works in the interval of time [0, T].
The goal is to gather the gangsters with the maximal total prosperity in the restaurant by opening and closing the door appropriately.
?The second line of the input file contains the moments of time when gangsters come to the restaurant T1, T2, ..., TN, separated by spaces. ( 0 <= Ti <= T for i = 1, 2, ..., N)
?The third line of the input file contains the values of the prosperity of gangsters P1, P2, ..., PN, separated by spaces. ( 0 <= Pi <= 300 for i = 1, 2, ..., N)
?The forth line of the input file contains the values of the stoutness of gangsters S1, S2, ..., SN, separated by spaces. ( 1 <= Si <= K for i = 1, 2, ..., N)
All values in the input file are integers.
Description
N gangsters are going to a restaurant. The i-th gangster comes at the time Ti and has the prosperity Pi. The door of the restaurant has K+1 states of openness expressed by the integers in the range [0, K]. The state of openness can change by one in one unit of time; i.e. it either opens by one, closes by one or remains the same. At the initial moment of time the door is closed (state 0). The i-th gangster enters the restaurant only if the door is opened specially for him, i.e. when the state of openness coincides with his stoutness Si. If at the moment of time when the gangster comes to the restaurant the state of openness is not equal to his stoutness, then the gangster goes away and never returns.The restaurant works in the interval of time [0, T].
The goal is to gather the gangsters with the maximal total prosperity in the restaurant by opening and closing the door appropriately.
Input
?The first line of the input file contains the values N, K, and T, separated by spaces. (1 <= N <= 100 ,1 <= K <= 100 ,0 <= T <= 30000 )?The second line of the input file contains the moments of time when gangsters come to the restaurant T1, T2, ..., TN, separated by spaces. ( 0 <= Ti <= T for i = 1, 2, ..., N)
?The third line of the input file contains the values of the prosperity of gangsters P1, P2, ..., PN, separated by spaces. ( 0 <= Pi <= 300 for i = 1, 2, ..., N)
?The forth line of the input file contains the values of the stoutness of gangsters S1, S2, ..., SN, separated by spaces. ( 1 <= Si <= K for i = 1, 2, ..., N)
All values in the input file are integers.
Output
Print to the output file the single integer ?the maximal sum of prosperity of gangsters in the restaurant. In case when no gangster can enter the restaurant the output should be 0.Sample Input
4
10 20 10 16 8 1610 11 15 110 7 1 8
Sample Output
26
这个题目非常类似于数塔，赤裸裸的dp
做这个问题暴露出了几个问题：
刚开始超内存了，这个问题完全可以避免。而后在考虑数据怎么保存的问题高了很久，殊不知只要一个flag数组标记下就可。
然后考虑开门程度是否超前时间的问题，殊不知倒叙时间完全可以避免这些问题。
总结下还是没有熟练数塔这个模型，一定要引以为戒。不然做再多也是白费！！
这个问题再次证明了动态规划自底向上状态拓展的特性
状态方程 dp[t][k] 时间t是开门k所能达到的最大财富
代码 1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 struct node{
7 int t , p , s;
8 }temp[110];
9
10 int dp[2][110];
11 bool flag[30010];
12
13 int MAX(int a, int b ){
14 return a>b?a:b;
15 }
16
17
18 int main(){
19 int i, j , N , K , T;
20 memset(dp , 0 , sizeof(dp));
21 memset(flag , false ,sizeof(flag));
22
23 scanf("%d %d %d",&N ,&K ,&T);
24 for(i=0 ; i<N ; i++){
25 scanf("%d" , &temp[i].t);
26 flag[ temp[i].t ] = 1;
27 }
28 for(i=0 ; i<N ; i++){
29 scanf("%d" , &temp[i].p);
30 }
31 for(i=0 ; i<N ; i++){
32 scanf("%d" , &temp[i].s);
33 }
34
35 int ans=0;
36
37 for(i=T ; i>=0 ; i--){
38 ans = 1-ans;
39 for(j=1 ; j<=K ; j++){
40 dp[ans][j] = MAX(dp[1-ans][j-1] , dp[1-ans][j]);
41 dp[ans][j] = MAX(dp[ans][j] , dp[1-ans][j+1]);
42 }
43 dp[ans][0] = MAX(dp[1-ans][0] , dp[1-ans][1]);
44
45 if(flag[i]){
46 for(j=0 ; j<N ; j++){
47 if(temp[j].t == i)
48 dp[ ans ][ temp[j].s ] += temp[j].p;
49 }
50 }
51 }
52
53 printf("%d\n" , dp[ans][0] );
54 return 0;
55 }
相关阅读 更多 +
