【第66题】背包10连刷之完全被爆：[USACO10JAN] Cheese Towers S

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

struct edge {
    int v, h;
} a[105];

int dp[1005];

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, t, k;
    cin >> n >> t >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].v >> a[i].h;
        for (int j = a[i].h; j <= t * 5 / 4; ++j) {
            // 因为整体少了4/5，所以原有的高度就是现有的 * （5/4），其他就是个裸的完全背包
            dp[j] = max(dp[j], dp[j - a[i].h] + a[i].v); 
        }
    }
    int ans = dp[t];
    for (int i = 0; i < n; ++i)
        if (a[i].h >= k) {
            // 对于每个大奶酪枚举其在顶端（因为这样才能关照到下面每个奶酪嘛）的最大价值
            ans = max(ans, dp[(t - a[i].h) * 5 / 4] + a[i].v); 
        }
    cout << ans;
    return 0;
}