总结

在常规的选择DP的键时，空间或时间复杂度可能无法接受，这时我们可以考虑转换键值的位置，以此获得更优的复杂度

E - Maximum Glutton

地址

官方题解写的也很不错

这里常规的思路一定是定义$dp[i][j]$表示，甜度为$i$、咸度为$j$时可以吃到的最多菜肴数

但是这样时空复杂度都无法接受

考虑到$n$的值较小，从$n$入手，把值(数量)与键(咸度)转化，定义新的数组$dp[i][j][k]$表示从前$i$个菜肴中选恰好$j$个，甜度为$k$，此时最小的咸度

void SINGLE_TEST(int CUR) {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    // 从前i个菜肴中选恰好j个，甜度为k，此时最小的咸度
    vector dp(n + 1, vector(n + 1, vector(x + 1, INF)));
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        for (int j = 1; j <= i; j++) {
            for (int k = a[i]; k <= x; k++) {
                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][k - a[i]] + b[i]);
            }
        }
    }
    int ans = -1;
    for (int j = n; j >= 0; j--) {
        for (int k = 0; k <= x; k++) {
            if (dp[n][j][k] <= y) {
                cout << min(j + 1, n) << "\n";
                return;
            }
        }
    }
}