Description：

一个奶酪塔高度最大为 $T$ 。 $N$ 块奶酪。第 $i$ 块高度为 $H_i$ （一定是 $5$ 的倍数），价值为 $V_i$ 。一个奶酪如果在它上方有高度 $\ge K$ 的奶酪，它的高度就会变成原来的 $4/5$ 。求最大价值和。

$1\le n \le 1000,1\le t \le 100$

Solution：

如果没有 $4/5$ ，那么就是一个完全背包，贪心的考虑整个塔要么没有大奶酪，要么最上方的是大奶酪，对于第二种情况，枚举最上面的奶酪，那么整个塔的高度最高就是 $(T-h[k])\times 5/4$ ，直接去背包数组中查即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,t,k;

#define MAXN 110

#define MAXT 1010

int v[MAXN],h[MAXN];

int f[MAXT];

int main()

{

	scanf("%d%d%d",&n,&t,&k);

	for(int i = 1;i <= n;++i)scanf("%d%d",&v[i],&h[i]);

	for(int i = 1;i <= n;++i)

		for(int j = h[i];j <= t * 5 / 4;++j)

			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;

}