完全背包
这题要考虑到怪兽的数目100000很多，但是生命值1000和防御力10很小，并且招数种类1000也不大，（根据抽屉原理）说明有很多生命值或者防御力重复的怪兽。因此我们没有必要一个怪兽一个是怪兽大，只要对每种生命值和防御力的怪兽进行每种招数的转移即可。
dp[i][j]表示消灭生命值为i,防御力为j的怪兽最少消耗的冰晶石数
dp[i][j] = min ( dp[i][j], dp[i-(p[t]-j)][j] + k[t])
然后注意边界处理即可。
这道题复习如何memset无穷大，和如何设INF
以及比较INF的大小时，用<比用!=快。
这道题也复习了处理前贪心剔除无用数据（虽然在这道题中不影响）。
还有最坑的害我一直TLE的是判断什么时候输入结束需要判断输入的数的个数。。。以前不是不用也可以吗？。。。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> using namespace std; #define N 100010 #define M 1010 #define INF 0x3f3f3f3f long long ans; int ma,mb,n,m,x; int a[N],b[N],k[M],p[M]; int dp[1010][11]; int best[1010]; int main() { while (scanf("%d%d", &n, &m)==2) { ma = mb = 0; for (int i=1;i<=n;i++) scanf("%d%d", a+i, b+i), ma = max(ma, a[i]), mb = max(mb, b[i]); memset(best, 0x3f, sizeof(best)); for (int i=1;i<=m;i++) { scanf("%d%d", k+i, p+i); if (best[p[i]] <= k[i] || p[i] == 0) {m--;i--;continue;} best[p[i]] = k[i]; } memset(dp, 0x3f, sizeof(dp)); for (int j=0;j<=mb;j++) dp[0][j] = 0; for (int i=1;i<=ma;i++) for (int j=0;j<=mb;j++) for (int t=1;t<=m;t++) { x = p[t] - j; if (x<=0) continue; if (i < x) dp[i][j] = min(dp[i][j], k[t]); else dp[i][j] = min(dp[i][j], dp[i-x][j] + k[t]); } ans = 0; for (int i=1;i<=n;i++) if (dp[a[i]][b[i]] < INF) ans+= dp[a[i]][b[i]]; else {ans = -1;break;} printf("%I64d\n", ans); } }