[BZOJ1606] [Usaco2008 Dec] Hay For Sale 购买干草 (dp)

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

  The wagon holds 7 volumetric units; three bales are offered for sale with
volumes of 2, 6, and 5 units, respectively.

Sample Output

7 //最大可以背出来的体积

HINT

  Buying the two smaller bales fills the wagon.

Source

  Silver

Solution

  暴力dp可以水过我会乱说?

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[5005];
 4 bool f[50005];
 5 int main()
 6 {
 7     int ans, c, h;
 8     scanf("%d%d", &c, &h);
 9     for(int i = 1; i <= h; i++)
10         scanf("%d", a + i);
11     f[0] = true;
12     for(int i = 1; i <= h; i++)
13         for(int j = c - a[i]; ~j; j--)
14             if(f[j]) f[j + a[i]] = true;
15     for(int i = 1; i <= c; i++)
16         if(f[i]) ans = i;
17     printf("%d\n", ans);
18     return 0;
19 }

时间: 05-24

[BZOJ1606] [Usaco2008 Dec] Hay For Sale 购买干草 (dp)的相关文章

[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 The wagon holds

BZOJ 1606 Hay For Sale 购买干草

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int v,n,r[5050],dp[50050];int main(){ scanf("%d%d",&v,&n); for (int i=1;i<=n;i++) scanf("%d",&r[i]); for (int i=1;i<=n;i++) for

[BZOJ] 1618: [Usaco2008 Nov]Buying Hay 购买干草

1618: [Usaco2008 Nov]Buying Hay 购买干草 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1216  Solved: 633[Submit][Status][Discuss] Description 约翰的干草库存已经告罄,他打算为奶牛们采购H(1≤H≤50000)磅干草,他知道N(1≤N≤100)个干草公司,现在用1到 N给它们编号.第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅,需要的开销为Ci(l≤Ci≤5

bzoj1618[Usaco2008 Nov]Buying Hay 购买干草*

bzoj1618[Usaco2008 Nov]Buying Hay 购买干草 题意: n种物品,每种无限个,重量为pi,费用为ci,要求总重量超过h的前提费用最小.求最小费用.n≤100,m≤50000. 题解: dp.f[i][j]=min(f[i-1][j],f[i][j-p[i]]+c[i]),边界f[0][0]=0,f[0][1..m+mx]=INF.最后在f[n][m..m+mx]中找一个最小的. 代码: 1 #include <cstdio> 2 #include <cstr

1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 574  Solved: 226[Submit][Status] Description Farmer John新买的干草打包机的内部结构大概算世界上最混乱的了,它不象普通的机器一样有明确的内部传动装置,而是,N (2 <= N <= 1050)个齿轮互相作用,每个齿轮都可能驱动着多个齿轮. FJ

[BZOJ1607][Usaco2008 Dec]Patting Heads 轻拍牛头

1607: [Usaco2008 Dec]Patting Heads 轻拍牛头 Time Limit: 3 Sec  Memory Limit: 64 MBSubmit: 2590  Solved: 1361[Submit][Status][Discuss] Description 今天是贝茜的生日,为了庆祝自己的生日,贝茜邀你来玩一个游戏. 贝茜让N(1≤N≤100000)头奶牛坐成一个圈.除了1号与N号奶牛外,i号奶牛与i-l号和i+l号奶牛相邻.N号奶牛与1号奶牛相邻.农夫约翰用很多纸条装

[BZOJ1589][Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 719  Solved: 408 [Submit][Status][Discuss] Description 每年万圣节,威斯康星的奶牛们都要打扮一番,出门在农场的N(1≤N≤100000)个牛棚里转悠,来采集糖果.她们每走到一个未曾经过的牛棚,就会采集这个棚里的1颗糖果. 农场不大,所以约翰要想尽

bzoj 1590: [Usaco2008 Dec]Secret Message 秘密信息

1590: [Usaco2008 Dec]Secret Message 秘密信息 Description 贝茜正在领导奶牛们逃跑.为了联络,奶牛们互相发送秘密信息. 信息是二进制的,共有M(1≤M≤50000)条.反间谍能力很强的约翰已经部分拦截了这些信息,知道了第i条二进制信息的前bi(l<bi≤10000)位.他同时知道,奶牛使用N(1≤N≤50000)条密码.但是,他仅仅了解第J条密码的前cj(1≤cj≤10000)位. 对于每条密码J,他想知道有多少截得的信息能够和它匹配.也就是说,有多

[Usaco2008 Nov]Buying Hay 购买干草[背包]

Description 约翰的干草库存已经告罄,他打算为奶牛们采购日(1≤日≤50000)磅干草. 他知道N(1≤N≤100)个干草公司,现在用1到N给它们编号.第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅,需要的开销为Ci(l≤Ci≤5000)美元.每个干草公司的货源都十分充足,可以卖出无限多的干草包.    帮助约翰找到最小的开销来满足需要,即采购到至少H磅干草. Input 第1行输入N和日,之后N行每行输入一个Pi和Ci. Output 最小的开销. Sample Input