CF762D Maximum path

一种不一样的做法

首先，因为是 ((1,1) o (3,n)) 的简单路径上的点权之和的最大值，所以显然只会在第 (2) 行进行“向左”的操作。

可以发现，每次向左一定会取到一个 (3) 行 (x) 列的子矩阵中的所有数，其中 (x) 是向左的次数。

如图，向左的次数是 (6)，所以它取到了一个 (3 imes 6) 的子矩阵中的数。

设 (f_{i,j}) 为 ((1,1) o (i,j)) 的简单路径上的点权之和的最大值，所以我们可以把只能往上、下、右走的做法，添加上两种转移：

[egin{aligned} f_{1,x}+a_{3,y}+sum_{j=1}^3sum_{k=x+1}^{y-1} a_{j,k}& o f_{3,y},forall x,yin [1,n],x<y \ f_{3,x}+a_{1,y}+sum_{j=1}^3sum_{k=x+1}^{y-1} a_{j,k}& o f_{1,y},forall x,yin [1,n],x<y end{aligned}]

其中 ( o) 指取 (max)，即可得到此题的做法。前缀和优化后，时间复杂度为 (mathcal{O}(n))。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &_x){
	_x=0;int _f=1;
	char ch=getchar();
	while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
	while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
	_x*=_f;
}
template<typename T,typename... Args> void Read(T &_x,Args& ...others){
	Read(_x);Read(others...);
}
typedef long long ll;
const int N=1e5+5;
const ll Inf=0x3f3f3f3f3f3f3f3fLL;
int n;ll a[4][N],f[4][N];
int main(){
	// freopen("CF762D.in","r",stdin);
	// freopen("CF762D.out","w",stdout);
	Read(n);
	For(i,1,3){
		For(j,1,n) Read(a[i][j]);
	}
	ll now=a[1][1]+a[2][1]+a[3][1],now1=-Inf;
	f[1][1]=a[1][1],f[2][1]=a[1][1]+a[2][1],f[3][1]=a[1][1]+a[2][1]+a[3][1];
	For(i,2,n){
		f[1][i]=max({f[1][i-1],f[2][i-1]+a[2][i],f[3][i-1]+a[3][i]+a[2][i]})+a[1][i];
		f[2][i]=max({f[1][i-1]+a[1][i],f[2][i-1],f[3][i-1]+a[3][i]})+a[2][i];
		f[3][i]=max({f[1][i-1]+a[1][i]+a[2][i],f[2][i-1]+a[2][i],f[3][i-1]})+a[3][i];
		now1=max(now1,f[3][i-1])+a[1][i]+a[2][i]+a[3][i];
		now=max(now,f[1][i-1])+a[1][i]+a[2][i]+a[3][i];
		f[1][i]=max(f[1][i],now1);
		f[3][i]=max(f[3][i],now);
	}
	printf("%lld
",f[3][n]);
	return 0;
}