题解：AT_abc431_d [ABC431D] Robot Customize

· · 题解

题目传送门

思路

看完题目发现裸的背包 \text{dp}。

我们发现题目要求 O(N^3) 的做法。而既然是背包，值域 V 为 \displaystyle\sum_{i=1}^N W_i，由于 W_i 和 N 同阶。不妨认为值域取到 N^2。则枚举 i 是 N，再乘上值域，得到了 O(N^3) 的背包做法。

初始化全部赋上极小值。题目取 \max。不难找到状态转移方程：

dp_{i,j}=\displaystyle\max_{j\in[0,V]}{dp_{i-1,j}+B_i}\\ dp_{i,j+W_i}=\displaystyle\max_{j\in[0,V-W_i]}{dp_{i-1,j}+H_i}

显然可以证明。然后我们发现空间会有 O(N^3)\approx1.25\times10^8。

又因为每个 i 所要更新的 dp_{i,j} 仅有 dp_{i-1,j} 转移而来，不放用滚动数组优化空间。空间复杂度优化为 O(N^2)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=505;
const int V=250000;
int n,w[N],a[N],b[N],dp[2][V+5],ans=LLONG_MIN,sum;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld%lld",w+i,a+i,b+i);
    for(int i=1;i<=V;i++) dp[0][i]=LLONG_MIN;dp[0][0]=0;
    for(int i=1;i<=n;i++){
        int f1=i%2,f2=(i-1)%2;
        for(int j=0;j<=V;j++) dp[f1][j]=LLONG_MIN;
        for(int j=0;j<=V;j++) dp[f1][j]=max(dp[f1][j],dp[f2][j]+b[i]);
        for(int j=0;j+w[i]<=V;j++) dp[f1][j+w[i]]=max(dp[f1][j+w[i]],dp[f2][j]+a[i]);
        sum+=w[i]; 
    }
    for(int i=0;i<=sum/2;i++) ans=max(ans,dp[n%2][i]);
    printf("%lld",ans);
    return 0;
}

撒花！