P1510 精卫填海

admin

https://www.luogu.org/problemnew/show/P1510
【问题描述】

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

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

输入输出格式
输入格式：
输入文件的第一行是三个整数：v、n、c。

从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式：
输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出’Impossible’（不带引号）。

输入输出样例
输入样例#1：
100 2 10
50 5
50 5
输出样例#1：
0
输入样例#2：
10 2 1
50 5
10 2
输出样例#2：
Impossible
说明
【数据范围】

对于20%的数据，0<n<=50。

对于50%的数据，0<n<=1000。

对于100%的数据，0<n<=10000，所有读入的数均属于[0,10000]，最后结果<=c。

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int V,n,c,ans=-1,vi,ki;
   
4. long long dp[10001];
   
5. int main()
   
6. {
   
7.     cin>>V>>n>>c;
   
8.     for(int i=1; i<=n; i++)
   
9.     {
   
10.         cin>>vi>>ki;
    
11.         for(int j=c; j>=ki; j--)
    
12.         {
    
13.             dp[j]=max(dp[j],dp[j-ki]+vi);
    
14.             if(dp[j]>=V)ans=max(ans,c-j);
    
15.         }
    
16.     }
    
17.     if(ans==-1)cout<<"Impossible";
    
18.     else cout<<ans;
    
19.     return 0;
    
20. }
    

复制代码

type尧

1. //
   
2. #include<iostream>
   
3. #include<cstdio>
   
4. #include<cstdlib>
   
5. #include<algorithm>
   
6. #define maxn 10010
   
7. using namespace std;
   
8. int v,n,c;
   
9. struct node{
   
10.         int v,u;       
    
11. }rock[maxn];
    
12. string st="Impossible";
    
13. int f[maxn];
    
14. void read()
    
15. {
    
16.         cin>>v>>n>>c;
    
17.         for(int i=1;i<=n;i++)
    
18.                 cin>>rock[i].v>>rock[i].u;
    
19.         return;
    
20. }
    
21. void work()
    
22. {
    
23.         read();
    
24.         for(int i=1;i<=n;i++)
    
25.                 for(int j=c;j>=rock[i].u;j--)
    
26.                         f[j]=max(f[j],f[j-rock[i].u]+rock[i].v);
    
27.         for(int i=0;i<=c;i++)
    
28.                 if(f[i]>=v){
    
29.                         cout<<c-i;
    
30.                         return;
    
31.                 }
    
32.         cout<<st;
    
33.         return;
    
34. }
    
35. int main()
    
36. {
    
37.         work();
    
38.         return 0;
    
39. }
    

复制代码