bzoj1606[Usaco2008 Dec]Hay For Sale 购买干草*

bzoj1606[Usaco2008 Dec]Hay For Sale 购买干草

题意：

容器体积为c，n个物体，每个有一个体积，求不超过容器能放入的最大体积。n≤5000，c≤50000

题解：

裸01背包。

代码：

 1 #include 
 2 #include 
 3 #include 
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define dec(i,j,k) for(int i=j;i>=k;i--)
 6 #define maxn 50100
 7 using namespace std;
 8 
 9 inline int read(){
10     char ch=getchar(); int f=1,x=0;
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
13     return f*x;
14 }
15 int n,c,f[maxn];
16 int main(){
17     c=read(); n=read();
18     inc(i,1,n){
19         int a=read(); dec(j,c,a)f[j]=max(f[j],f[j-a]+a);
20     }
21     printf("%d",f[c]); return 0;
22 }

20160727

转载于:https://www.cnblogs.com/YuanZiming/p/5712970.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！