题目描述
原题题面
FJ要建一个奶酪塔，高度最大为T。他有N种奶酪。第i种奶酪的高度为Hi（一定是5的倍数），价值为Vi。一块高度Hi>=K的奶酪被称为大奶酪，一个奶酪如果在它上方有大奶酪（如果有多块就只算一次），它的高度Hi就会变成原来的4/5.。FJ想让他的奶酪塔价值和最大。请你求出这个最大值。
输入格式：
第一行三个数N,T,K，意义如上所述。 接下来n行，每行两个数V_i,h_i（注意顺序）
输出格式：
奶酪塔的最大价值
输入输出样例
输入 #1
3 53 25
100 25
20 5
40 10
输出 #1
240
【解题思路】：
（1）用数组f记录体积未被压缩时的最大价值
（2）用数组ff记录体积被压缩后的最大价值
（3）for循环枚举去掉最上面奶酪体积的最大价值ff[j]加上最上面的奶酪价值v[i]
（4）比较压缩前后的最大价值（如果不存在大奶酪，则ff数组均为0，输出压缩前最大价值；反之，压缩后最大价值必然大于等于压缩前最大价值）
【AC代码】：
#include <bits/stdc++.h>
#define M(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
#define MOD 10000007
using namespace std;inline void read(int &x){
char ch=getchar(),c=ch;x=0;while(ch<'0' || ch>'9'){
c=ch;ch=getchar();}while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}if(c=='-')x=-x;
}int n,T,k,ans,i,j;
int f[2000],v[1000],h[1000];int main(){
read(n),read(T),read(k);for(i=1;i<=n;i++) {
read(v[i]),read(h[i]);for(j=h[i];j<=T*5/4;j++)f[j]=max(f[j],f[j-h[i]]+v[i]);}ans=f[T];for(i=1;i<=n;i++)if(h[i]>=k)ans=max(ans,f[(T-h[i])*5/4]+v[i]);printf("%d\n",ans);return 0;
}