题目链接
中文题 ， 题意一目了然。
将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背包 ， 所以要注意循环顺序 ， 不要做成了完全背包了。
代码如下：
代码语言：javascript复制 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("%dn",ans);
71 }
72
73 int main()
74 {
75 scanf("%d",&T);
76 while(T--)
77 {
78 read_cal();
79 }
80 return 0;
81 }
