洛谷 P1510 精卫填海

题解：一道简单的01背包，把思维稍稍转变一下，试想求当花费体力为v时，能带最多的石头的体积是多少。

如果dp[vmax]还没有达到东海剩余的体积，就无解，否则，就循环找寻消耗的最小体力。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 10005
 6 
 7 using namespace std;
 8 
 9 int dp[maxn],w[maxn],c[maxn];
10 int vsea,vmax,n;
11 
12 int main()
13 {
14     scanf("%d%d%d",&vsea,&n,&vmax);
15     for(int i=1;i<=n;i++)
16         scanf("%d%d",&c[i],&w[i]);
17     for(int i=1;i<=n;i++)
18         for(int v=vmax;v>=w[i];v--)
19             dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
20     if(dp[vmax]<vsea) 
21     {
22         printf("Impossible");
23         return 0;
24     } 
25     for(int i=1;i<=vmax;i++)
26         if(dp[i]>=vsea) 
27         {
28             printf("%d",vmax-i);
29             return 0;
30         }
31     return 0;
32 }