题目链接： http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1003
题目大意： a[i], b[i] | 0 <= i <= n .................... k[j], p[j] | 0 <= j <= m, n个魔王， m中法术方式， 每个法术攻击p[j]， 消耗k[j]水晶， 每个魔王a[i]生命, b[i]护甲， 攻击必须先打穿护甲， 求杀死所有魔王的最少水晶数。
解题思路： dp[i][j] 表示一个魔王血量为i 护甲为 j 的时候， 杀死它需要的最少水晶， 哦对了， 水晶无限， 所以就转换成n个完全背包问题， 再加和。
代码： 下面我的代码有错， 不知道哪儿错了
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int maxn = 1e5+100; const int maxm = 1e3 + 100; const int maxa = 1e3 + 100; const int maxb = 15; using namespace std; const int INF = 0x3fffffff; int a[maxn]; int b[maxn]; int k[maxm]; int p[maxm]; int dp[maxa][maxb]; // dp(i, j)生命值为i , 防御值为 j 的时候消灭它花费最少 int main() { int n, m; while( scanf( "%d%d", &n, &m ) == 2 ) { int defend = 0; int attack = 0; int ma = 0; for( int i = 1; i <= n; i++ ) { scanf( "%d%d", a+i, b+i ); defend = max( defend, *(b+i) ); ma = max( ma, *(a+i) ); } for( int i = 1; i <= m; i++ ) { scanf( "%d%d", k+i, p+i ); attack = max( attack, *(p+i) ); } if( attack <= defend ) { printf( "-1 " ); continue; } for( int i = 0; i <= ma; i++ ) { for( int j = 0; j <= defend; j++ ) { if( i == 0 ) dp[0][j] = 0; else dp[i][j] = INF; } } for( int i = 1; i <= ma; i++ ) { for( int j = 0; j <= defend; j++ ) { for( int t = 1; t <= m; t++ ) { if( j > p[t] ) continue; else if( i - (p[t]-j) >= 0 ) { dp[i][j] = min( dp[i][j], dp[i-(p[t]-j)][j]+k[t] ); } else dp[i][j] = min( dp[i][j], dp[0][j]+k[t] ); } } } long long res = 0; for( int i = 1; i <= n; i++ ) { res += dp[a[i]][b[i]]; } printf( "%lld ", res ); } return 0; }
徐文栋的AC代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 100100; const int maxm = 1010; const int maxp = 10010; const int maxa = 1010; const int maxb = 11; const LL inf = (1LL << 60); int n, m; int a[maxn], b[maxn], k[maxm], p[maxm]; LL f[maxa][maxb]; signed main() { // freopen("in", "r", stdin); while(~scanf("%d %d",&n,&m)) { for(int i = 0; i < maxa; i++) { for(int j = 0; j < maxb; j++) { f[i][j] = inf; } } for(int i = 0; i < maxb; ++i) f[0][i] = 0; int ha = -1, hb = -1; for(int i = 1; i <= n; i++) { scanf("%d%d",&a[i], &b[i]); ha = max(ha, a[i]); hb = max(hb, b[i]); } for(int i = 1; i <= m; i++) scanf("%d%d",&k[i], &p[i]); for(int i = 1; i <= ha; i++) { for(int j = 0; j <= hb; j++) { for(int x = 1; x <= m; x++) { if(j >= p[x]) continue; if(i + j - p[x] > 0) f[i][j] = min(f[i][j], f[i+j-p[x]][j] + k[x]); else f[i][j] = min(f[i][j], f[0][j] + k[x]); } } } LL ret = 0; bool flag = 0; for(int i = 1; i <= n; i++) { if(f[a[i]][b[i]] == inf) { flag = 1; break; } ret += f[a[i]][b[i]]; } if(flag) puts("-1"); else printf("%I64d ", ret); } return 0; } Close BestCoder Contest System 2.0
思考： 一开始我想的状态是前i个魔王再加上一个状态来求解， 太天真， 每一个魔王都是独立的， 所以dp方程不管怎么都没有办法转移 ，很难受， 然后我想是不是应该像《劲歌金曲》那样不关心前面的状态， 用滚动数组d[i]， i表示血量， 同样面临着无法转移的问题， 后来问了人才知道， 事先预处理每个魔王， 再加和， 自己好蠢。 其实不是蠢的问题， 我想问题就是自己还是没有理清思路， 不能够找到真正和结果相联系的状态， 还得多做题。