题解 P2979 【[USACO10JAN]奶酪塔Cheese Towers】

reek · 2017-10-20 15:02:15 · 题解

如果没有大奶酪，这道题就是一道裸的完全背包。

稍微思考能够发现，最有解只有两种情况：要么整个奶酪塔上都没有大奶酪，要么奶酪塔的最上面一块是大奶酪。因为如果在奶酪塔的中间位置有一个大奶酪，那么显然把这块大奶酪提到奶酪塔的最顶端不会使答案变劣。

对于第一种情况，直接做完全背包即可。

对于第二种情况，我们可以枚举最上面的那块大奶酪i，用v[i]+f[(T-h[i])*5/4]更新ans。

最后两种情况取max即可。

#include<iostream>
#include<cstdio>
using namespace std;
int n,T,k,ans,f[2000],v[1000],h[1000];
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 j=h[i];j<=T*5/4;j++)
        f[j]=max(f[j],f[j-h[i]]+v[i]);
    }
    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]);
    printf("%d\n",ans);
    return 0;
}