题目大意：

给出一张大小为 $n\ast m$ 的矩阵，每一块都有一个权值 $a_{i,j}$ ，可以随机选择起点，并且只能向右拐或向前走，不能碰到走过的路或走出图，求走过的路径权值和最大为多少。

数据范围：

$1\le n,m\le 32,|a_{i,j}|\le 10^4$

思路：

转移方程非常阴间。。。
看到数据范围 $n,m\le 32$ 发现使用搜索时间上过不去，所以考虑使用 $DP$ 。
我们可以发现所有合法的路径一定包含一个或两个回环，如图：

所以我们可以先 $DP$ 求出所有的回环，再将回环拼接在一起就可以了。
可以发现每一个回环的区别有：
$1.$ 顺时针和逆时针（如图2的两个回环）
$2.$ 结束的点（如图1在右下角，图2第一个回环在右下角，第二个回环在左下角）

所以可以设 $f_{x,y,xx,yy,0/3,0/1}$ 表示这个回环是在左上角为 $(x,y)$ ，右下角为 $(xx,yy)$ 的矩阵上，且结束点在左上（左下，右上，右下）角，形状为顺时针（逆时针）的最大路径价值和。

如图，以结束点在右上角为例，则可以转移到的图形有三种：
$1.$ 可以由上一个结束点也在这个点的相同回环转移，如图1。
$2.$ 可以由往下缩短一格后再加上此点的回环转移，如图2。
$3.$ 可以由一个回环加上一段横行（竖行）转移，如图3。

所以要先用前缀和记录所有的横行和竖行的权值前缀和，以便 $3$ 的转移。
并且图形是由小图形到大图形进行转移，所以要枚举这个回环的长和宽来进行 $DP$
转移的状态有 $8$ 种，慢慢仔细打是可以打完的。

对与两个回环相接，可以得出结论：两个回环的方向相反。
之后枚举一个矩形的左上角和右下角，再分别枚举横，纵坐标的分割点，根据回环方向和回环的结束点更新答案就可以了。

$DP$ 的时间复杂度为 $O(n^4)$ ，枚举更新答案的时间复杂度为 $O(n^5)$ ，能过。

AC代码

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,a[40][40],ans=-21000000;
int f[40][40][40][40][4][2];
int hang[40][40],lie[40][40];
int Max(int a,int b,int c,int d)
{
	int tot=max(max(max(a,b),c),d);
	return tot;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 {
	 	scanf("%d",&a[i][j]);
	 	hang[i][j]=hang[i][j-1]+a[i][j];
	 	lie[i][j]=lie[i-1][j]+a[i][j];
	 	for(int k=0;k<=3;k++)
	 	 for(int l=0;l<=1;l++)
	 	 f[i][j][i][j][k][l]=a[i][j];
	 	ans=max(ans,a[i][j]);
	 }	
	for(int len1=1;len1<=n;len1++)//DP
	  for(int len2=1;len2<=m;len2++)
	  {
	  	if(len1==len2&&len1==1)
	  	continue;
	  	for(int x=1;x+len1-1<=n;x++)
	  	 for(int y=1;y+len2-1<=m;y++)
	  	 {
	  	 	 int xx=x+len1-1,yy=y+len2-1;
	  	     f[x][y][xx][yy][0][0]=Max(f[x][y][xx-1][yy][0][0],f[x][y+1][xx][yy][0][0],f[x+1][y][xx][yy][0][0]+a[x][yy],f[x][y][xx][yy-1][3][0]+lie[xx][yy]-lie[x-1][yy]);
			 f[x][y][xx][yy][1][0]=Max(f[x][y][xx-1][yy][1][0],f[x][y][xx][yy-1][1][0],f[x][y+1][xx][yy][1][0]+a[x][y],f[x+1][y][xx][yy][0][0]+hang[x][yy]-hang[x][y-1]);
			 f[x][y][xx][yy][2][0]=Max(f[x+1][y][xx][yy][2][0],f[x][y][xx][yy-1][2][0],f[x][y][xx-1][yy][2][0]+a[xx][y],f[x][y+1][xx][yy][1][0]+lie[xx][y]-lie[x-1][y]);
			 f[x][y][xx][yy][3][0]=Max(f[x+1][y][xx][yy][3][0],f[x][y+1][xx][yy][3][0],f[x][y][xx][yy-1][3][0]+a[xx][yy],f[x][y][xx-1][yy][2][0]+hang[xx][yy]-hang[xx][y-1]);
			 f[x][y][xx][yy][0][1]=Max(f[x][y][xx-1][yy][0][1],f[x][y+1][xx][yy][0][1],f[x][y][xx][yy-1][0][1]+a[x][yy],f[x+1][y][xx][yy][1][1]+hang[x][yy]-hang[x][y-1]);
			 f[x][y][xx][yy][1][1]=Max(f[x][y][xx-1][yy][1][1],f[x][y][xx][yy-1][1][1],f[x+1][y][xx][yy][1][1]+a[x][y],f[x][y+1][xx][yy][2][1]+lie[xx][y]-lie[x-1][y]);			
			 f[x][y][xx][yy][2][1]=Max(f[x+1][y][xx][yy][2][1],f[x][y][xx][yy-1][2][1],f[x][y+1][xx][yy][2][1]+a[xx][y],f[x][y][xx-1][yy][3][1]+hang[xx][yy]-hang[xx][y-1]);
			 f[x][y][xx][yy][3][1]=Max(f[x+1][y][xx][yy][3][1],f[x][y+1][xx][yy][3][1],f[x][y][xx-1][yy][3][1]+a[xx][yy],f[x][y][xx][yy-1][0][1]+lie[xx][yy]-lie[x-1][yy]);
		 }
	  }
	for(int len1=1;len1<=n;len1++)//枚举 
	 for(int len2=1;len2<=m;len2++)
	 {
	 	if(len1==len2&&len1==1)
	 	continue;
	 	for(int x=1;x+len1-1<=n;x++)
	 	 for(int y=1;y+len2-1<=m;y++)
	 	 {
	 	     int xx=x+len1-1,yy=y+len2-1;
	 	     for(int k=0;k<=3;k++)
	 	      for(int l=0;l<=1;l++)
	 	      ans=max(ans,f[x][y][xx][yy][k][l]);
			 for(int k=x;k<xx;k++)
			 {   
			   ans=max(ans,f[x][y][k][yy][2][0]+f[k+1][y][xx][yy][1][1]);
			   ans=max(ans,f[x][y][k][yy][3][1]+f[k+1][y][xx][yy][0][0]);
			 }	
			 for(int k=y;k<yy;k++)
			 {
			 	
			 	ans=max(ans,f[x][y][xx][k][3][0]+f[x][k+1][xx][yy][2][1]);
				ans=max(ans,f[x][y][xx][k][0][1]+f[x][k+1][xx][yy][1][0]);
			 }
		 }
	 }
	 printf("%d\n",ans);
}