专栏文章

题解：AT_abc431_d [ABC431D] Robot Customize

cchenzefan
AT_abc431_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8u1fd
此快照首次捕获于
2025/12/01 22:27
3 个月前
此快照最后确认于
2025/12/01 22:27
3 个月前
查看原文
题目传送门

思路

看完题目发现裸的背包 dp\text{dp}。
我们发现题目要求 O(N3)O(N^3) 的做法。而既然是背包，值域 VV 为 ∑i=1NWi\displaystyle\sum_{i=1}^N W_i，由于 WiW_i 和 NN 同阶。不妨认为值域取到 N2N^2。则枚举 ii 是 NN，再乘上值域，得到了 O(N3)O(N^3) 的背包做法。
初始化全部赋上极小值。题目取 max⁡\max。不难找到状态转移方程：
dpi,j=max⁡j∈[0,V]dpi−1,j+Bidpi,j+Wi=max⁡j∈[0,V−Wi]dpi−1,j+Hidp_{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(N3)≈1.25×108O(N^3)\approx1.25\times10^8。
又因为每个 ii 所要更新的 dpi,jdp_{i,j} 仅有 dpi−1,jdp_{i-1,j} 转移而来，不放用滚动数组优化空间。空间复杂度优化为 O(N2)O(N^2)。

代码

CPP
#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;
}
撒花！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...