[HDOJ6082] 度度熊与邪恶大魔王（枚举，完全背包）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6082

枚举所有怪兽可能的生命值和防御值，以此为代价，对魔法值和伤害值做完全背包，每次求出击杀怪物的最小花费，求答案的时候把各种组合的最小花费加起来即可。

#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;
}