华师一附中OI组

标题: P1510 精卫填海 [打印本页]
作者: admin    时间: 2018-7-3 16:38
标题: P1510 精卫填海
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。
作者: 黄煦喆    时间: 2018-8-26 19:48
  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尧    时间: 2018-11-4 18:59
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2