题解：P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train

给一个

O(n^3\log n)

的写法。

前言

为了方便，把

2\sim n

的物品下标换到

1\sim {n-1}

，且将

n

减

1

，

d

除以

2

，这样可以将距离从

2*(i-1)

变为

i

，显然对答案无影响。

思路

考虑朴素

dp

，设计

f_{i,j}

表示考虑前

i

个数，用了

j

的路程的最大价值，那其实就是一个空间为

d

的背包，每个物品体积为

i

，价值是转移区间里前

w

大的数，记

ans_{l,r}

表示区间

l\sim r

中前

w

大的数，转移显然：

f_{i,j}=\max_{k=0}^{k<i}f_{k,j-i}+ans_{k+1,i}

暴力转移复杂度

O(n^4)

，考虑优化。

容易发现

ans_{l,r}

是满足四边形不等式的，证明显然，那么直接决策单调性，分治优化

dp

即可。不会的看这里。

复杂度

O(n^3\log n)

，注意要特判

w=1

的情况。

代码

注意不要开 long long，空间会炸。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=460;
int n,w,d;
int f[N][N*N],ans[N][N],a[N];
int tmp[N];
int query(int l,int r){
	int ans=0,c=0;
	for(int i=l;i<=r;i++) tmp[++c]=a[i],ans+=a[i];
	if(c<=w) return ans;
	sort(tmp+1,tmp+c+1);
	ans=0;
	for(int i=c;i>=c-w+1;i--) ans+=tmp[i];
	return ans;
}
void solve(int i,int l,int r,int L,int R){
	if(l>r) return;
	int mid=l+r>>1,mx=0,k=0;
	for(int j=L;j<=R;j++)
		if(f[j][mid-i]+ans[j+1][i]>mx){
			mx=f[j][mid-i]+ans[j+1][i];
			k=j;
		}
	f[i][mid]=mx;
	solve(i,l,mid-1,L,k);
	solve(i,mid+1,r,k,R);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>w>>d;
	--n,d/=2;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(w==1){
		int ans=0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=d;j++)
				if(j>=i) f[i][j]=max(f[i-1][j],f[i-1][j-i]+a[i]),ans=max(ans,f[i][j]);
				else f[i][j]=f[i-1][j];
		return cout<<ans,0;
	}
	for(int l=1;l<=n;l++)
		for(int r=l;r<=n;r++)
			ans[l][r]=query(l,r);
	for(int i=1;i<=n;i++) solve(i,i,d,0,i-1);
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=d;j++)
			ans=max(ans,f[i][j]);
	cout<<ans;
	return 0;
}

题解：P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train

文章操作

前言

思路

代码

相关推荐

评论

题解：P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train