题目描述
FJ要建一个奶酪塔，高度最大为T。他有N种奶酪。第i种奶酪的高度为Hi（一定是5的倍数），价值为Vi。一块高度Hi>=K的奶酪被称为大奶酪，一个奶酪如果在它上方有大奶酪（如果有多块就只算一次），它的高度Hi就会变成原来的4/5.。FJ想让他的奶酪塔价值和最大。请你求出这个最大值。
输入格式：
第一行三个数N,T,K，意义如上所述。 接下来n行，每行两个数V_i,h_i（注意顺序）
输出格式：
奶酪塔的最大价值
* Line 1: Three space-separated integers: N, T, and K
* Lines 2..N+1: Line i+1 contains two space separated integers: V_i and H_i
* Line 1: The value of the best tower FJ can build
3 53 25
100 25
20 5
40 10
240
【解题思路】
如果没有大奶酪，这道题就是一道裸的完全背包。
稍微思考能够发现，最有解只有两种情况：要么整个奶酪塔上都没有大奶酪，要么奶酪塔的最上面一块是大奶酪。因为如果在奶酪塔的中间位置有一个大奶酪，那么显然把这块大奶酪提到奶酪塔的最顶端不会使答案变劣。
对于第一种情况，直接做完全背包即可。
对于第二种情况，我们可以枚举最上面的那块大奶酪i，用v[i]+f[(T-h[i])*5/4]更新ans。
最后两种情况取max即可。
【code】
1 #include <cstdio>
2 using namespace std;
3 int n,t,k;
4 int f[2005],v[1005],h[1005],ans;
5 inline int Max(int a,int b){
6 return a>b?a:b;
7 }
8 int main(){
9 scanf("%d%d%d",&n,&t,&k);
10 for(register int i=1;i<=n;i++){
11 scanf("%d%d",&v[i],&h[i]);
12 for(register int j=h[i];j<=t*5/4;j++)
13 f[j]=Max(f[j],f[j-h[i]]+v[i]);
14 }
15 ans=f[t];
16 for(register int i=1;i<=n;i++)
17 if(h[i]>=k)
18 ans=Max(ans,f[(t-h[i])*5/4]+v[i]);
19 printf("%d\n",ans);
20 return 0;
21 }
原文：https://www.cnblogs.com/66dzb/p/11257387.html