8.31
思路： 这是一道简单DP 题，两句话题解。 1. 完全背包打表，可以得到DP[i][j]，i，j 表示生命值为i的龙牙兵防御力为j 时所需的宝石数。 2. 再跑一遍01 背包f[i][j]，计算卫除掉前i个士兵，卫宫剩余血量为j，最少使用多少个宝石 3. 最后答案就是 min f[n][i]
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define N 3005 #define LL long long #define del(a,b) memset(a,b,sizeof(a)) using namespace std; const LL inf = 5000000000ll; int n, m, w, x, y; int g[N], dp[1005]; LL f[N][2005]; struct sde{ int l, f, t, cost; }sd[N]; bool cmp(sde aa, sde bb){ return aa.f < bb.f; } void get_dp(int f){//一维存，for防御力 del(dp, 127); dp[0] = 0; for(int i=1; i<=1000; i++){ for(int j=0; j<i; j++) dp[i] = min(dp[i], dp[j]+g[i-j+f]); } } int main(){ freopen ("fsn.in", "r", stdin); freopen ("fsn.out", "w", stdout); scanf("%d%d%d", &n, &m, &w); del(g, 127); for(int i=1; i<=n; i++) scanf("%d%d%d", &sd[i].l, &sd[i].f, &sd[i].t); for(int i=1; i<=m; i++){ scanf("%d%d", &x, &y); g[y] = min(g[y], x); }//法术攻击产生y的伤害，最少需要x个宝石 for(int i=1000; i; i--) g[i] = min(g[i], g[i+1]);//消除不优的法术 sort(sd+1, sd+n+1, cmp); int last = -1; for(int i=1; i<=n; i++){ if(sd[i].f != last){ last = sd[i].f; get_dp(last); } sd[i].cost = dp[sd[i].l]; } del(f, 127); for(int i=0; i<=w; i++) f[0][i] = 0;//除掉前i个士兵，剩余血量为j，最少使用多少个宝石 for(int i=0; i<n; i++){ for(int j=0; j<=w; j++){ f[i+1][j] = min(f[i+1][j], f[i][j]+sd[i+1].cost); if(j - sd[i+1].t >= 0) f[i+1][j-sd[i+1].t] = min(f[i+1][j-sd[i+1].t], f[i][j]); } } LL ans = inf; for(int i=0; i<=w; i++) ans = min(ans, (LL)f[n][i]); cout << ans; return 0; }