总结

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

E - Maximum Glutton

官方题解写的也很不错

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void SINGLE_TEST() 
{
    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<vector<vector<int>>> dp(n+1,vector<vector<int>>(n+1,vector<int>(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 ;
            }
        }
    }
}

DP优化：键值转换

交换键值获得更优的时间复杂度

总结

E - Maximum Glutton