题解 P1510 【精卫填海】

SIGSEGV

2018-07-05 12:34:25

Solution

dalao们的算法好复杂啊...... 蒟蒻看不懂........ 背包问题就没必要弄得那么复杂嘛! ```cpp #include<bits/stdc++.h> using namespace std; int dp[20005],v,n,c,t1,t2; int main () { scanf("%d%d%d",&v,&n,&c); memset(dp,-1,sizeof(dp));//重置 dp[0] = c;//初始化 for (int i = 0;i < n;i++) { scanf("%d%d",&t1,&t2); for (int i = v + 500;i >= t1;--i) /*500是为了防止出现 v完不成但v+k(k>0)能够完成的情况 这个数应该够大 要自己估 但看dalao们题解好像并不用这样做*/ dp[i] = max(dp[i],dp[i - t1] - t2);//dp常例 但方程要换一下 } int ans = -1; for (int i = v;i <= v + 500;i++) ans = max(ans,dp[i]); if (ans == -1) printf("Impossible");else cout << ans;//输出 return 0; } ```