题目链接：点击打开链接
题目中文，容易理解，不再叙述
思路：
开始想到的是完全背包，对于每个怪兽，分别去利用完全背包得到最后DP结果，可是怪兽数量（取值1~10^5）太大，复杂度达到O(10^9)，所以一定会超时，而且思路不是最佳的
正确的解法就是普通的DP，dp[i][t]表示防御力为i（取值0~10），生命值为t（取值1~1000）的怪兽被打败需要的最小晶石数，再加入j（取值1~1000）表示技能，直接枚举i，j，t（其中i，j要满足harm[j] >= i），由状态转移方程得最后结果，然后再去处理每个怪兽。复杂度为O(10^7)
// 度度熊与邪恶大魔王.cpp 运行/限制：202ms/1000ms #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define INF 0x3f3f3f3f int stone[1005], harm[1005]; int life[100005], pro[100005]; int dp[15][1005]; int main(){ int n, m; while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i < n; i++) { scanf("%d%d", &life[i], &pro[i]); } for (int i = 0; i < m; i++) { scanf("%d%d", &stone[i], &harm[i]); } memset(dp, INF, sizeof(dp)); for (int i = 0; i <= 10; i++) {//防御力 for (int j = 0; j < m; j++) {//技能 if (harm[j] < i) continue; for (int t = 1; t <= 1000; t++) {//生命力 if (harm[j] - i >= t) dp[i][t] = min(dp[i][t], stone[j]); else dp[i][t] = min(dp[i][t], dp[i][t - (harm[j] - i)] + stone[j]); } } } long long re = 0; int flag = 1; for (int i = 0; i < n; i++) { if (dp[pro[i]][life[i]] == INF) { flag = 0; break; } re += dp[pro[i]][life[i]]; } if (flag) printf("%lld\n", re); else printf("-1\n"); } return 0; } TLE的完全背包代码：
// 度度熊与邪恶大魔王.cpp Time Limit Exceeded #include "stdafx.h" #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; int life[100005], pro[100005]; int stone[1005], harm[1005]; int dp[1005]; #define INF 0x3f3f3f3f int main(){ int n, m,re, flag; while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i < n; i++) { scanf("%d%d", &life[i], &pro[i]); } for (int i = 0; i < m; i++) { scanf("%d%d", &stone[i], &harm[i]); } re = 0, flag = 1; for (int i = 0; i < n; i++) {//怪兽 10^5 memset(dp, INF, sizeof(dp)); for (int j = 0; j < m; j++) {//技能 10^1 if (harm[j] < pro[i]) continue; for (int t = 1; t <= life[i]; t++) {//生命值 10^3 if (harm[j] - pro[i] >= t) { dp[t] = min(dp[t], stone[j]); } else { dp[t] = min(dp[t], dp[t - (harm[j] - pro[i])] + stone[j]); } } } if (dp[life[i]] == INF) { printf("-1\n"); flag = 0; break; } re += dp[life[i]]; } if (flag) { printf("%d\n", re); } else { printf("-1\n"); } } return 0; }
