HLUOJ蛋糕塔（USACO奶酪塔）_蛋糕塔加载指令

USACO奶酪塔

对于这道题呢，是DP，确切地说是背包，还是完全背包，今天早上也就只打了这题，因为有位童鞋一直在“不耻下问”，让我对这题逐步有了深刻的理解 {(￢_￢)智商三岁}，于是认为一定要来水一下博客。

这个奶酪塔在我们的 “偶剧诶”（OJ）成功地发酵变成了“蛋糕塔”，老刘想掩人耳目是不可能的，因为这道题两位大佬都给我们讲过，而且文件输入输出还是“cheese”，更坑的是还多带一个点！！这是坑了多少人

经过我的疯狂吐槽后，我们就不在追究这波操作了。进入正题：

题目描述（原谅我的复制粘贴）
Hl高中要举行一场蛋糕塔比赛。（有的吃吗？ヾ(◍°∇°◍)ﾉﾞ）

学校会提供N种不同类型的蛋糕，第i种蛋糕的高度为Hi(5 <= H_i <= T)，营养价值为Vi（1 <= Vi<= 1,000,000)，并且保证所有蛋糕的高度为5的整数倍（这个我认为并没有什么卵用），每种类型的蛋糕没有数量限制。

蛋糕塔比赛的规则就是要求按照提供的蛋糕，垒成一个高度不超过T(1 <= T <= 1,000)的蛋糕塔，并且要求这个蛋糕塔所有蛋糕的营养价值累加和最高。

因为蛋糕不是很结实（学校的应该很结实才对），参加比赛的小x发现一个现象，如果某块蛋糕的高度超过K，那么这块蛋糕下面的所有蛋糕的高度都将被压缩为自己高度的4/5，但是营养价值不会丢失。发现这个情况后的小x很兴奋，现在他想知道，如何安排自己的蛋糕塔，能让营养价值最高。

输入格式
第一行三个整数：N，T和K；

接下来N行，每行两个整数：Vi 和 Hi。

输出格式
一行，一个整数，表示答案。

样例数据
input

3 53 25
100 25
20 5
40 10
output
240
有3种蛋糕，蛋糕塔的高度限制为53，高度必须超过25的蛋糕才能将其下面的蛋糕高度压缩。我们按照下面的方法来垒蛋糕：

           个数 高度    价值
         高->[1]   25    100
             [2]   4     20  
             [3]   8     40  
             [3]   8     40  
         底->[3]   8     40
1
2
3
4
5
6
7

最上的蛋糕将下方的蛋糕都压缩为4/5.最大价值为240

解：
非常幸运的，我们第一眼就发现这是一个完全背包再进行一小点操作，而且一系列的一系列都和蛋糕的高度扯上了关系，因此我们设f[i]表示蛋糕塔高度为i时的最优值，但是由于塔的高度会被大蛋糕所压缩，因此改进表示为未被压缩的高度（即实际高度）为i的蛋糕塔的最高营养价值。正因为是未被压缩过的，又因为压缩时会变成实际的4/5，所以塔的实际最高 高度为t/(4/5)即t*5/4

接下来，我们看一看完全背包的模板：

for (int i = 1; i <= n; ++i) {
    for (int j = w[i]; j <= v; ++j) {
        f[j] = max(f[j], f[j - c[i]] + v[i]);
    }
}
1
2
3
4
5

一系列过程参考：https://www.cnblogs.com/Kalix/p/7622102.html
为了好理解我们将遗忘
既然f[i]记录的是当蛋糕塔实际高度为i时的最优营养值，对于当下的小蛋糕(i 这个i不同于f[i]的i)来说，可以放一个或放n个知道放满，即高度为t（这是对于压缩后来说的）那么实际上是可以放 这个小蛋糕的高度~t/(4/5) 因此完全背包的内循环确定为：for(int j=h[i];j<=t*5/4;j++) 依次更新蛋糕塔高度为j时的最优值。
温故而知新：f[j]=max(f[j],f[j-h[i]]+v[i]);max中f[j] 表示不加当前的蛋糕，f[j-h[i]] 表示在到达指定高度的前提下，放当下这块蛋糕的最优值，整个f[j-h[i]]+v[i] 表示放下这块蛋糕的最优值
ans用来记录答案即最后最优值f[t]
但是问题来了f[]不是用来表示实际高度的吗？最大值不应该是f[t5/4]吗？为什么会是f[t]呢？
在这里需要说明一下：f[]在此时表示的是一堆小蛋糕叠在一起的实际高度的最优值，但是也不能排除小蛋糕刚好搭到t，大蛋糕就不能进行压缩，因此实际高度=名义上的压缩高度。
最后就是传说中的一点点小操作了，用大蛋糕进行压缩，更新ans。因为要求最优值，所以我们不能让蛋糕塔空出位置不利用，因此确定压缩后的高度 一定为t，那么除去大蛋糕的高度，被压缩的小蛋糕的高度就为t-h[i]，又因为f[]记录的是实际高度而不是压缩高度，压缩高度又可以以5/4转换为实际高度，所以ans=max(ans,f[(t-h[i])*5/4]+v[i]);

那么接下来，上代码：

//要么最优都是小cake，要么就是有一个大cake是在顶上的
//对于只有小cake直接用完全背包来做
//最后在顶端放大cake对ans进行更新 
#include<bits/stdc++.h>
using namespace std;
int v[5050],h[5050];
int f[5050];
int main()
{
	freopen("cheese..in","r",stdin);
	freopen("cheese..out","w",stdout); 
	int n,t,k;
	cin>>n>>t>>k;
	for(int i=1;i<=n;i++)
	 cin>>v[i]>>h[i];
	for(int i=1;i<=n;i++)
	 for(int j=h[i];j<=t*5/4;j++)
//对于高度来说，因为当下只考虑了小cake，
//所以这个高度是实际，即目的高度的4/5
//因此/(4/5)即*5/4 
	  f[j]=max(f[j],f[j-h[i]]+v[i]);
    int ans=f[t];
	for(int i=1;i<=n;i++)
	 if(h[i]>=k)
	  ans=max(ans,f[(t-h[i])*5/4]+v[i]);
	cout<<ans<<endl; 
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28