HDU 1574 RP问题

题目链接

中文题，题意一目了然。

将a b c 进行处理一下。

当a > 0 时：

需要当前RP小于等于b才能触发此事件，触发此事件时，人品增加a ，获益值增加c(此时c为负)

当a < 0 时

需要当前RP大于等于b才能触发此事件，触发此事件时，人品增加a(此时a为负) ，获益值增加c

那么可以设dp[i]为RP为i时，获得的最大获益值。

因为b可能为负（一个人的RP可能为负），所以对b进行小小的处理，增加10000 因为 b >= -10000 加上10000之后就变0了

状态转移方程为：

dp[i+a] = max(dp[i] + c , dp[i+a]);

0-1背包，所以要注意循环顺序，不要做成了完全背包了。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <map>
 7 #include <list>
 8 #include <queue>
 9 #include <stack>
10 #include <string>
11 #include <algorithm>
12 #include <iterator>
13 using namespace std;
14 #define MAXN 20020
15 #define INF 0x3f3f3f3f
16 #define MOD 1000000007
17 #define eps 1e-6
18 #define LL long long
19 bool vis[MAXN];
20 int dp[MAXN];
21 int T,n;
22 void init()
23 {
24     memset(dp , 0 , sizeof(dp));
25     memset(vis , false , sizeof(vis));
26     dp[10000] = 0;
27     vis[10000] = true;
28 }
29 void read_cal()
30 {
31     int a,b,c;
32     init();
33     scanf("%d",&n);
34     for(int i = 0; i < n; i ++)
35     {
36         scanf("%d %d %d",&a,&b,&c);
37         b += 10000;
38         if(a >= 0 )
39         {
40             for(int j = b; j >= 0; j --)
41                 if(vis[j])
42                 {
43                     if(!vis[j+a])
44                     {
45                         vis[j+a] = true;
46                         dp[j+a] = dp[j] + c;
47                     }
48                     else 
49                         dp[j+a] = max(dp[j] + c , dp[j + a]);
50                 }
51         }
52         else if(a < 0)
53         {
54             for(int j = b; j < MAXN; j ++)
55                 if(vis[j])
56                 {
57                     if(!vis[j+a])
58                     {
59                         vis[j+a] = true;
60                         dp[j+a] = dp[j] + c;
61                     }
62                     else 
63                         dp[j+a] = max(dp[j] + c , dp[j+a]);
64                 }
65         }
66     }
67     int ans = -INF;
68     for(int i = 0; i < MAXN; i ++)
69         if(vis[i]) ans = max(ans , dp[i]);
70     printf("%d
",ans);
71 }
72 
73 int main()
74 {
75     scanf("%d",&T);
76     while(T--)
77     {
78         read_cal();
79     }
80     return 0;
81 }

View Code