传纸条是一道典型的多进程动态规划题，四维状态的状态定义很容易想到，具体定义如下：d[i1,j1,i2,j2]表示第一次从起点走到(i1,j1)这个点，第二次从起点走到(i2,j2)这个点所获得的最大值。状态转移方程也很容易写出：

d[i1,j1,i2,j2]=max(d[i1-1,j1,i2-1,j2],d[i1-1,j1,i2,j2-1],d[i1,j1-1,i2-1,j2],d[i1,j1-1,i2,j2-1])+a[i1,j1]+a[i2,j2]；if i1=i2 and j1=j2 then d[i1,j1,i2,j2]=d[i1,j1,i2,j2]-a[i1,j1]；

关于这一点在本空间的博客中已经提到。

但是这样的状态定义却重复计算了许多子问题。递推需要四层循环，前两层是固定了第一次的终点，然后开始推第二次的终点；试想第一次走到(i,j)这个点，递推完成，下次递推第一次走到(i,j+1)这个点的情况，即将第二次走到的位置从(1,1)推到(m,n)。直观地去想，这样做是不是多出了许多运算？或者是没有充分利用重叠子问题？

发现对于一个m,n的矩阵，共有m+n-1条对角线，而每次走下一步，都是从一条对角线，走到下一条对角线。于是有了一个另外一个状态定义：d[i,j,k]表示在第i条对角线上，第一次走到行坐标为j的位置，第二次走到行坐标为k的位置。这样的定义就避免了重复计算，因为在第i条对角线的情况只取决于第i-1条对角线的情况，不需要从头开始重新计算，可以想象一下这样定义的程序执行过程。而且可以用滚动数组优化空间，最终只需要d[2,51,51]的空间就足够了！和之前d[51,51,51,51]的空间复杂度好太多了。在时间上也是一个极大的优化，最终全部数据加在一起会在0.2s内解决，之前需要1.9s左右。

以下是我的代码：

#include<stdio.h>
#define max(a,b) (a>b?a:b)
long m,n,a[51][51],d[2][51][51]={0};
long begin(long x)
{
    if(x>=1&&x<=n) return 1;
    if(x>n&&x<=n+m-1) return x-n+1;
}
long end(long x)
{
    return (x<m?x:m);
}
int main()
{
    freopen("message.in","r",stdin);
    freopen("message.ans","w",stdout);
    long i,j,k;
    scanf("%ld%ld",&m,&n);
    for(i=1;i<=m;i++)
      for(j=1;j<=n;j++)
        scanf("%ld",&a[i][j]);
    for(i=1;i<=n+m-1;i++)
      for(j=begin(i);j<=end(i);j++)
        for(k=begin(i);k<=end(i);k++)
        {
           d[i%2][j][k]=max(d[(i-1)%2][j][k],d[(i-1)%2][j-1][k]);
           d[i%2][j][k]=max(d[i%2][j][k],d[(i-1)%2][j][k-1]);
           d[i%2][j][k]=max(d[i%2][j][k],d[(i-1)%2][j-1][k-1]);
           d[i%2][j][k]+=a[j][i-j+1]+a[k][i-k+1];
           if(j==k)
             d[i%2][j][k]-=a[j][i-j+1];
        }
    printf("%ld\n",d[(n+m-1)%2][m][m]);
return 0;
}