题解 P1510 【精卫填海】

2018-07-05 12:34:25


dalao们的算法好复杂啊...... 蒟蒻看不懂........

背包问题就没必要弄得那么复杂嘛!

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