题意：一个人物有K(K<=7)种技能，每种技能都有bi,ci,di值，表示该技能不能点超过bi次，每点一次加ci,点满bi次有一个附加得分di。然后还有N件武器，武器本身会有能力加成，然后每个武器可能会对应着多种的技能，当你装备了这些武器的时候对应的技能的技能点＋1（但是武器的技能点不能重复，也就是如果a武器和b武器都能提高技能1的话，如果你两件都装备了只算一次）。现在这些都给定给你了，问的是假如现在你有X个技能点（X<=35）和最多不能携带超过Y件武器（Y<=100），求你所能获得的最大的分数。
思维的切入口在于K的数量级是7，一下子就能联想到2进制的位压，然后很自然的联想到了武器重复不会增加，所以会选择定义这么一种状态dp[n][y][sta],表示的是前n个物品选了y件达到sta状态（就是K个技能有没被加的位压）的时候所获得的最大的分数（这里先不把满技能点的分算进去）。然后就是for循环更新状态了，n的那一维可以滚动（懒得思考方向了），然后一开始dp[0][0][0]=-1,其他设为－1表示状态不存在。 dp完后我们就完成了第一项操作了。
现在就是点技能点的时候，点技能点的时候我们怎么样才知道最大可以点到多少呢，枚举就可以了！我们定义第二个dps[sta]的数组，这个表示的是如果当前状态为sta，那么我点完技能点的时候所能获得的最大加成，由于每个bi<=5，所以每次求一次sta最多不需要超过6^7(实际上会小一点)，所以求完一遍总是够时间的。
接下来就是dps[sta]+dp[N&1][Y][sta]里取最大值了(当然不存在的状态就不要管它了)。
想转移想了我颇久了－ －0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#include<queue>#define ll long long#define maxn 120#define maxk 10using
namespace std;int
K, N;int
b[maxk], c[maxk], d[maxk];int
G[maxn][maxk];int
a[maxn];int
X, Y;int
dp[2][maxn][1 << 8];int
dps[1 << 8];int
dfs(int
sta, int
step, int
cnt){ if
(step >= K) return
0; int
cur = 0; if
((sta >> step) & 1) cur++; int
res = 0; for
(int i = 0; i <= b[step] - cur&&i<=cnt; i++){ if
(cur + i == b[step]) res = max(res, dfs(sta, step + 1, cnt - i) + d[step]+i*c[step]); else
res = max(res, dfs(sta, step + 1, cnt - i)+i*c[step]); } return
res;}int
main(){ while
(cin >> K >> N) { for
(int i = 0; i < K; i++) scanf("%d%d%d", b + i, c + i, d + i); memset(G, 0, sizeof(G)); int
mi; for
(int i = 0; i < N; i++){ scanf("%d%d", a + i, &mi); int
ti; for
(int j = 0; j < mi; j++){ scanf("%d", &ti); G[i][ti - 1] = 1; } } scanf("%d%d", &X, &Y); memset(dp, -1, sizeof(dp)); dp[0][0][0] = 0; for
(int i = 0; i < N; i++){ memcpy(dp[(i + 1) & 1], dp[i & 1], sizeof(dp[(i + 1) & 1])); for
(int x = 0; x <= Y-1; x++){ for
(int sta = 0; sta < (1 << K); sta++){ if
(dp[i & 1][x][sta] == -1) continue; int
nsta = sta; int
inc = a[i]; for
(int j = 0; j < K; j++){ if
(G[i][j] && !((sta >> j) & 1)){ inc += c[j]; nsta |= 1 << j; } } dp[(i + 1) & 1][x + 1][nsta] = max(dp[(i + 1) & 1][x + 1][nsta], dp[i & 1][x][sta] + inc); } } } for
(int i = 0; i < 1 << K; i++){ dps[i] = dfs(i, 0, X); } for
(int i = 0; i < 1 << K; i++){ if
(dp[N & 1][Y][i] != -1){ dps[i] += dp[N & 1][Y][i]; } else
dps[i] = -1; } int
ans = 0; for
(int i = 0; i < 1 << K; i++){ ans = max(ans, dps[i]); } cout << ans << endl; } return
0;} |
ZOJ3718 Diablo II(状态压缩dp),布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3637380.html