#include <iostream>

#include <cstdio>

using namespace std;

typedef int arr[51][51][51][51];

typedef int arr1[51][51];

int n,m,i,j,x1,x2,Y1,y2,x0,Y0,yf,xf,cur;

arr1 sum;

arr f,vcut1,hcut1,vcut2,hcut2;

inline int area(int x1,int x2,int Y1,int y2)

{

return sum[x2][y2]+sum[x1][Y1]-sum[x1][y2]-sum[x2][Y1];

}

int main()

{

scanf("%d%d",&n,&m);

for (x2=0;x2<=n;x2++)

for (y2=0;y2<=m;y2++)

if (x2&&y2)

for (x1=x2-1;x1>=0;x1--)

for (Y1=y2-1;Y1>=0;Y1--)

if (x2-x1==1&&y2-Y1==1)

{

scanf("%d",sum[x2]+y2);

sum[x2][y2]+=sum[x2-1][y2]+sum[x2][y2-1]-sum[x2-1][y2-1];

f[x1][x2][Y1][y2]=0;

vcut1[x1][x2][Y1][y2]=hcut1[x1][x2][Y1][y2]=-1;

vcut2[x1][x2][Y1][y2]=hcut2[x1][x2][Y1][y2]=-1;

}

else

{

switch (y2-Y1)

{

case 1:

yf=0x6fffffff;

vcut1[x1][x2][Y1][y2]=vcut2[x1][x2][Y1][y2]=-1;

break;

case 2:

yf=f[x1][x2][Y1][y2-1]+f[x1][x2][Y1+1][y2];

vcut1[x1][x2][Y1][y2]=vcut2[x1][x2][Y1][y2]=Y1+1;

break;

default:

yf=0x6fffffff;

for (Y0=vcut1[x1][x2][Y1][y2-1];Y0<=vcut2[x1][x2][Y1+1][y2];Y0++)

{

cur=f[x1][x2][Y1][Y0]+f[x1][x2][Y0][y2];

if (yf>=cur)

{

if (yf>cur)

vcut1[x1][x2][Y1][y2]=Y0;

yf=cur;

vcut2[x1][x2][Y1][y2]=Y0;

}

}

}

switch (x2-x1)

{

case 1:

xf=0x6fffffff;

hcut1[x1][x2][Y1][y2]=hcut2[x1][x2][Y1][y2]=-1;

break;

case 2:

xf=f[x1][x2-1][Y1][y2]+f[x1+1][x2][Y1][y2];

hcut1[x1][x2][Y1][y2]=hcut2[x1][x2][Y1][y2]=x1+1;

break;

default:

xf=0x6fffffff;

for (x0=hcut1[x1][x2-1][Y1][y2];x0<=hcut2[x1+1][x2][Y1][y2];x0++)

{

cur=f[x1][x0][Y1][y2]+f[x0][x2][Y1][y2];

if (xf>=cur)

{

if (xf>cur)

hcut1[x1][x2][Y1][y2]=x0;

xf=cur;

hcut2[x1][x2][Y1][y2]=x0;

}

}

}

f[x1][x2][Y1][y2]=area(x1,x2,Y1,y2)+min(xf,yf);

// printf("f[%d][%d][%d][%d]=%d\n",x1,x2,Y1,y2,f[x1][x2][Y1][y2]);

// printf("vcut1[%d][%d][%d][%d]=%d ",x1,x2,Y1,y2,vcut1[x1][x2][Y1][y2]);

// printf("vcut2[%d][%d][%d][%d]=%d\n",x1,x2,Y1,y2,vcut2[x1][x2][Y1][y2]);

// printf("hcut1[%d][%d][%d][%d]=%d ",x1,x2,Y1,y2,hcut1[x1][x2][Y1][y2]);

// printf("hcut2[%d][%d][%d][%d]=%d\n",x1,x2,Y1,y2,hcut2[x1][x2][Y1][y2]);

}

else

sum[x2][y2]=0;

printf("%d",f[0][n][0][m]);

system("pause");

}

结果WA了，不加优化的又过了。为什么为什么？！