A50542.礼物 题解

首先 $O(n^2m)$ 的暴力转移 DP 非常好写，不再说明。考虑优化 DP。

容易想到，每一次购买是独立的，相互不依赖、不影响。所以可以预处理一下。

预处理出进行一次购买，花费为 $i$ 时候，小 P 所能拿到的最大价值。这个过程 $O(n^2)$ 枚举即可。

然后就是朴实无华的完全背包了。

时间复杂度：$O(n^2+m^2)$.

空间复杂度：$O(n+m)$.

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll c[5005],v[5005],a[5005],pre[5005],dp[5005];
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>c[i]>>v[i];
    for(ll i=1;i<=n;i++){
        for(ll j=i+1;j<=n;j++){
            if(c[i]+c[j]>m) continue;
            a[c[i]+c[j]]=max(min(v[i],v[j]),a[c[i]+c[j]]);
        }
    }
    for(ll i=2;i<=m;i++) pre[i]=max(a[i],pre[i-1]);
    for(ll i=2;i<=m;i++) for(ll j=i;j<=m;j++) dp[j]=max(dp[j-i]+pre[i],dp[j]);
    cout<<dp[m];
    return 0;
}