BZOJ2021: [Usaco2010 Jan]Cheese Towers

2021: [Usaco2010 Jan]Cheese Towers

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 184  Solved: 107
[Submit][Status]

Description

Farmer John wants to save some blocks of his cows‘ delicious Wisconsin cheese varieties in his cellar for the coming winter. He has room for one tower of cheese in his cellar, and that tower‘s height can be at most T (1 <= T <= 1,000). The cows have provided him with a virtually unlimited number of blocks of each kind of N (1 <= N <= 100) different types of cheese (conveniently numbered 1..N). He‘d like to store (subject to the constraints of height) the most valuable set of blocks he possibly can. The cows will sell the rest to support the orphan calves association. Each block of the i-th type of cheese has some value V_i (1 <= V_i <= 1,000,000) and some height H_i (5 <= H_i <= T), which is always a multiple of 5. Cheese compresses. A block of cheese that has height greater than or equal to K (1 <= K <= T) is considered "large" and will crush any and all of the cheese blocks (even other large ones) located below it in the tower. A crushed block of cheese doesn‘t lose any value, but its height reduces to just 4/5 of its old height. Because the height of a block of cheese is always a multiple of 5, the height of a crushed block of cheese will always be an integer. A block of cheese is either crushed or not crushed; having multiple large blocks above it does not crush it more. Only tall blocks of cheese crush other blocks; aggregate height of a tower does not affect whether a block is crushed or not. What is the total value of the best cheese tower FJ can construct? Consider, for example, a cheese tower whose maximum height can be 53 to be build from three types of cheese blocks. Large blocks are those that are greater than or equal to 25. Below is a chart of the values and heights of the various cheese blocks he stacks: Type Value Height 1 100 25 2 20 5 3 40 10 FJ constructs the following tower: Type Height Value top -> [1] 25 100 [2] 4 20 <- crushed by [1] above [3] 8 40 <- crushed by [1] above [3] 8 40 <- crushed by [1] above bottom -> [3] 8 40 <- crushed by [1] above The topmost cheese block is so large that the blocks below it are crushed. The total height is: 25 + 4 + 8 + 8 + 8 = 53 The total height does not exceed 53 and thus is ‘legal‘. The total value is: 100 + 20 + 40 + 40 + 40 = 240. This is the best tower for this particular set of cheese blocks. John要建一个奶酪塔,高度最大为T。他有N块奶酪。第i块高度为Hi(一定是5的倍数),价值为Vi。一块高度>=K的奶酪被称为大奶酪,一个奶酪如果在它上方有大奶酪(多块只算一次),它的高度就会变成原来的4/5.。。 很显然John想让他的奶酪他价值和最大。。 求这个最大值。。

Input

第一行分别是 N T K 接下来N行分别是 Vi Hi

Output

一行最大值

Sample Input

3 53 25
100 25
20 5
40 10

Sample Output

240

HINT

Source

Silver

题解:

这题比较有意思。

其实完全两次背包就可以解决,不过还有其他的方法。

做一次容积为 t*5/4的背包,然后 if(h[i]>=k)ans=max(ans,v[i]+f[(t-h[i])*5/4])

好写不容易出错。orz lyd。

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[110],b[110],f[2000],n,t,k,m,i,j,ans;
 5 int main()
 6 {
 7     cin>>n>>t>>k;
 8     m=t*5/4;
 9     for(i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
10     for(i=1;i<=n;i++)
11         for(j=0;j<=m-b[i];j++)
12             f[j+b[i]]=max(f[j+b[i]],f[j]+a[i]);
13     for(i=1;i<=m;i++) f[i]=max(f[i],f[i-1]);
14     ans=f[t];
15     for(i=1;i<=n;i++)
16         if(b[i]>=k) ans=max(ans,a[i]+f[(t-b[i])*5/4]);
17     cout<<ans<<endl;
18     return 0;
19 }

时间: 10-01

BZOJ2021: [Usaco2010 Jan]Cheese Towers的相关文章

2020: [Usaco2010 Jan]Buying Feed, II

2020: [Usaco2010 Jan]Buying Feed, II Time Limit: 3 Sec  Memory Limit: 64 MBSubmit: 220  Solved: 162[Submit][Status] Description (buying.pas/buying.in/buying.out 128M 1S) Farmer John needs to travel to town to pick up K (1 <= K <= 100) pounds of feed

洛谷 P2979 [USACO10JAN]奶酪塔Cheese Towers

P2979 [USACO10JAN]奶酪塔Cheese Towers 题目描述 Farmer John wants to save some blocks of his cows' delicious Wisconsin cheese varieties in his cellar for the coming winter. He has room for one tower of cheese in his cellar, and that tower's height can be at

bzoj 1783: [Usaco2010 Jan]Taking Turns

1783: [Usaco2010 Jan]Taking Turns Description Farmer John has invented a new way of feeding his cows. He lays out N (1 <= N <= 700,000) hay bales conveniently numbered 1..N in a long line in the barn. Hay bale i has weight W_i (1 <= W_i <= 2,0

bzoj usaco 金组水题题解(1)

UPD:我真不是想骗访问量TAT..一开始没注意总长度写着写着网页崩了王仓(其实中午的时候就时常开始卡了= =)....损失了2h(幸好长一点的都单独开了一篇)....吓得赶紧分成两坨....TAT.............. —————————————————————————————————————————————————————————————————————————————— 写(被虐)了整整一个月b站上usaco的金组题...然而到现在总共只写了100道上下TAT(当然是按AC人数降序排

[BZOJ] 1614: [Usaco2007 Jan]Telephone Lines架设电话线

1614: [Usaco2007 Jan]Telephone Lines架设电话线 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1806  Solved: 773[Submit][Status][Discuss] Description Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向电信公司支付一定的费用. FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废

BZOJ 1778: [Usaco2010 Hol]Dotp 驱逐猪猡

1778: [Usaco2010 Hol]Dotp 驱逐猪猡 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 563  Solved: 216[Submit][Status][Discuss] Description 奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡.猪猡的文明包含1到N (2 <= N <= 300)一共N个猪城.这些城市由M (1 <= M <= 44,850)条由两个不同端点A_j和B_j (1 <= A_j<

bzoj3396[Usaco2009 Jan]Total flow 水流*

bzoj3396[Usaco2009 Jan]Total flow 水流 题意: 求无环图的最大流.边数≤700. 题解: 管它有没有环.注意本题的节点标号既有大写字母,也有小写字母. 代码: 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #de

bzoj 1699: [Usaco2007 Jan]Balanced Lineup排队 分块

1699: [Usaco2007 Jan]Balanced Lineup排队 Time Limit: 5 Sec  Memory Limit: 64 MB Description 每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的

[2016-03-28][HDU][1078][FatMouse and Cheese]

时间:2016-03-28 17:40:34 星期一 题目编号:[2016-03-28][HDU][1078][FatMouse and Cheese] #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int maxn = 100 + 10; int a[maxn][maxn]; int dp[maxn][maxn]; int n ,k; int d