P1510 精卫填海

标签：体力 int 木石 P1510 填平 vector 精卫填海 dp

东海未填平的区域还需要至少体积为 v 的木石才可以填平，而西山上的木石还剩下 n 块，每块的体积和把它衔到东海需要的体力分别为 k 和 m。
精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为 c。
如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出 Impossible

1. 动态规划

每个木石是一个物品，体积是物品的价值，消耗体力是物品的质量，总体力c是总容量，
计算不同容量的最大价值，然后从小到大遍历，输出最小满足条件的容量时候的剩余容量

void maxval(int V,vector<int>&c,vector<int>&w,int v){
    int n = c.size();
    vector<int> dp(V+1);
    for(int i=0;i<n;i++)
        for(int j=V;j>=c[i];j--)
            dp[j] = max(dp[j],dp[j-c[i]]+w[i]);

    for(int j=0;j<=V;j++)
        if(dp[j]>=v){
            cout<<V-j;
            return;
        }
    cout<<"Impossible";
    return;
}

标签：体力,int,木石,P1510,填平,vector,精卫填海,dp
From： https://www.cnblogs.com/929code/p/17648933.html