「BZOJ1606」[Usaco2008 Dec] Hay For Sale 购买干草
Description
约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草． 顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，
他最多可以运回多少体积的干草呢？
Input
第1行输入C和H，之后H行一行输入一个Vi．
Output
最多的可买干草体积．
Sample Input
7 3 //总体积为7,用3个物品来背包
2
6
5
2
6
5
The wagon holds 7 volumetric units; three bales are offered for sale with
volumes of 2, 6, and 5 units, respectively.
Sample Output
7 //最大可以背出来的体积
题解
…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include<iostream> #include<cstdio> using namespace std; int c,h,a[5001];bool f[50001]; int main() { scanf("%d%d",&c,&h); for(int i=1;i<=h;i++)scanf("%d",&a[i]); f[0]=1; for(int i=1;i<=h;i++) for(int j=c;j>=a[i];j--) if(f[j-a[i]])f[j]=1; for(int i=c;i>=0;i--)if(f[i]){printf("%d",i);break;} return 0; } |
Subscribe
计数器 9774141
OI 课件=>
OI 课件=>