一种思路奇特的做法。
看到题目容易联想到背包dp，因为看上去很像。
但是我们并不知道上面有没有大奶酪。
所以我们不妨倒过来看，从上往下加奶酪。
设 \(dp(i,1/0)\) 表示当前从上往下的累加高度为 \(i\)，这之中有/无大奶酪。
显然，当我们考虑新加一个奶酪时，有：
\[\begin{cases} dp(i,0)=\max(dp(i-h_j,0)+v_j)\ \ (h_j<K)\\ dp(i,1)=\max(dp(i-h_j,0)+v_j)\ \ (h_j\geq K) \end{cases}\]然后对于 \(dp(i,1)\)，还有：
\[dp(i,1)=\max(dp(i-\frac{4}{5}h_j,1)+v_j) \]总的时间复杂度 \(O(nt)\)，听说 \(O(n^2t)\) 也能过……
#include<bits/stdc++.h>
#define N 110
#define T 1010
using namespace std;
int n,t,k,ans;
int v[N],h[N];
int dp[T][2];
int main()
{
scanf("%d%d%d",&n,&t,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&h[i]);
memset(dp,128,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<=t;i++)
{
for(int j=1;j<=n;j++)
{
if(i-h[j]>=0)
{
if(h[j]<k) dp[i][0]=max(dp[i][0],dp[i-h[j]][0]+v[j]);
else dp[i][1]=max(dp[i][1],dp[i-h[j]][0]+v[j]);
}
}
for(int j=1;j<=n;j++)
if(i-h[j]*4/5>=0)
dp[i][1]=max(dp[i][1],dp[i-h[j]*4/5][1]+v[j]);
ans=max(ans,max(dp[i][0],dp[i][1]));
}
printf("%d\n",ans);
return 0;
}