题意：一个人物有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
#pragma warning(disable:4996)#include#include #include #include #include #include #include #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;}