https://www.luogu.com.cn/problem/P1006

题意：一个棋盘，左上到右下，两条不相交的权值最大的路径，只首尾重合。

$d[i][j][x][y]$ 表示第一条路到 $（i，j）$ 第二条到 $（x，y）$

$d[i][j][x][y]=max(d[i-1][j][x-1][y],d[i-1][j][x][y-1],d[i][j-1][x-1][y],d[i][j-1][x][y-1])$

$+a[i][j]+a[x][y]$

枚举 $i,j,x,y$ 的时候$（i，j）$ 默认在 $（x，y）$ 下面，因为不能相交，总有一条在下面。当只有 $y=j+1$

有一点重合，判断一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MAX=50+10;
int m,n,a[MAX][MAX],d[MAX][MAX][MAX][MAX],f,e; 
int main(){
	freopen("in","r",stdin);
	sf(m);sf(n);
	fi(i,1,m+1)	
		fi(j,1,n+1)	
			sf(a[i][j]);
	fi(k,1,n+m){
		f= k>m ?m:k;
		e= k<m ?1:k-m+1;
		for(int i=f,j=e;i>0&&j<=n;i--,j++){
			for(int x=i-1,y=j+1;x>0&&y<=n;x--,y++){
				d[i][j][x][y]=max(d[i-1][j][x-1][y],max(d[i][j-1][x-1][y],d[i][j-1][x][y-1]));
				if(y-j>1) d[i][j][x][y]=max(d[i][j][x][y],d[i-1][j][x][y-1]);//此时会重叠 
				d[i][j][x][y]+=a[i][j]+a[x][y];
			}
		}
	}
	pf(d[m][n-1][m-1][n]);
	return 0;
}