华师一附中OI组

标题: P2925 [USACO08DEC]干草出售Hay For Sale [打印本页]
作者: admin    时间: 2018-10-14 10:52
标题: P2925 [USACO08DEC]干草出售Hay For Sale
https://www.luogu.org/problemnew/show/P2925

题目描述
农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车到农民Don的农场中买一些稻草给奶牛过冬。已知john的马车可以装的下C(1 <= C <=50,000)立方的稻草。
农民Don有H(1 <= H <= 5,000)捆体积不同的稻草可供购买，每一捆稻草有它自己的体积(1 <= V_i <= C)。面对这些稻草john认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。
现在给定马车的最大容积C和每一捆稻草的体积Vi，john如何在不超过马车最大容积的情况下买到最大体积的稻草？他不可以把一捆稻草分开来买。

输入输出格式
输入格式：
第一行两个整数，分别为C和H
第2..H+1行:每一行一个整数代表第i捆稻草的体积Vi

输出格式：

一个整数，为john能买到的稻草的体积。
输入输出样例
输入样例#1：
7 3
2
6
5
输出样例#1：
7
作者: 黄煦喆    时间: 2018-10-28 21:58
  1. #include<iostream>
  2. using namespace std;
  3. int const maxc=50000+10;
  4. int c,n,a[5001];
  5. bool dp[maxc]= {1};
  6. int main()
  7. {
  8.     cin>>c>>n;
  9.     for(int i=1; i<=n; i++)
  10.     {
  11.         cin>>a[i];
  12.         for(int j=c; j>=a[i]; j--)dp[j]=dp[j]||dp[j-a[i]];
  13.     }
  14.     int l=c;
  15.     while(!dp[l])l--;
  16.     cout<<l;
  17.     return 0;
  18. }
复制代码
作者: type尧    时间: 2018-11-4 18:50
  1. //
  2. #include<iostream>
  3. #include<cstdlib>
  4. #include<cstdio>
  5. #include<algorithm>
  6. #define maxh 10000
  7. #define maxc 100000
  8. using namespace std;
  9. int h,c;
  10. int v[maxh];
  11. int f[maxc];
  12. void read()
  13. {
  14.         cin>>c>>h;
  15.         for(int i=1; i<=h; i++) cin>>v[i];
  16.         return;
  17. }
  18. void work()
  19. {
  20.         read();
  21.         for(int i=1; i<=h; i++)
  22.                 for(int j=c; j>=v[i]; j--) {
  23.                         f[j]=max(f[j],f[j-v[i]]+v[i]);
  24.                         if(f[j]==c) {
  25.                                 cout<<c;
  26.                                 return;
  27.                         }
  28.                 }
  29.         cout<<f[c];
  30.         return;
  31. }
  32. int main()
  33. {
  34.         work();
  35.         return 0;
  36. }
复制代码




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