题目链接：
https://www.luogu.org/problem/P1006
题意：
一个n*m的网格，每个格子有一个值，要求从左上(1,1)找到两条到右下(m,n)不重合的路径且两条路径上格子的值的和最大，每次移动只能向下或向右(0<=m,n<=50)，起点(1,1)和终点(m,n)的值为0。
题解：
显然可以用四维dp(当然有些机智的巨佬发现可以用三维dp),一条路径走到(i,j),另一条走到(k,t),因为不能重合，所以第四重循环的t要从j+1开始，因为第一条路径走到(i,j)时,以(1,1),(1,j),(i,1),(i,j)为顶点的矩形内的点都已被第一条路径走过，而且以(1,1),(1,n),(i,1),(i,n)为顶点的矩形内还未走的点将被第一条路径走过。
状态转移方程:
dp[i][j][k][t]=max(dp[i-1][j][k-1][t]+a[i][j]+a[k][t],dp[i-1][j][k][t-1]+a[i][j]+a[k][t],dp[i][j-1][k-1][t]+a[i][j]+a[k][t],dp[i][j-1][k][t-1]+a[i][j]+a[k][t])
代码：
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std
;
int dp
[55][55][55][55];
int s
[55][55];
int main()
{
int m
,n
;
int a
[55][55];
cin
>>n
>>m
;
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++) cin
>>a
[i
][j
];
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
for(int k
=1;k
<=n
;k
++)
{
for(int t
=j
+1;t
<=m
;t
++)
dp
[i
][j
][k
][t
]=max(dp
[i
-1][j
][k
-1][t
]+a
[i
][j
]+a
[k
][t
],max(dp
[i
-1][j
][k
][t
-1]+a
[i
][j
]+a
[k
][t
],max(dp
[i
][j
-1][k
-1][t
]+a
[i
][j
]+a
[k
][t
],dp
[i
][j
-1][k
][t
-1]+a
[i
][j
]+a
[k
][t
])));
}
}
}
cout
<<dp
[n
][m
-1][n
-1][m
];
return 0;
}
