三取方格数

【问题描述】 背景 Background JerryZhou同学经常改编习题给自己做。 这天，他又改编了一题。。。。。 【描述 Description】 设有N*N的方格图，我们将其中的某些方格填入正整数， 而其他的方格中放入0。 某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。 在走过的路上，他取走了方格中的数。（取走后方格中数字变为0） 此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。 【输入格式 Input Format】 第一行:N (4<=N<=20) 接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0 【输出格式 Output Format】 一行，表示最大的总和。 【样例输入 Sample Input】 4 1 2 3 4 2 1 3 4 1 2 3 4 1 3 2 4 样例输出 Sample Output 39 注释 Hint 多进程DP 算法分析 可以用网络流来做 由于没做二取方格数；我一开始用一般DP；DP一次则把走过的路删去；3次DP； 只对了一组；看了题解后知道了我的算法虽然保证了3次DP的最优；但并不代表全局最优；是有反例的...... 其实可以用压缩数组的方法..因为每一阶段都只与上一阶段有关..滚动滚动数组..循环利用..不断再生..节约环保..{好像扯远了...-_-#}..不过节约时间起见..其实不用滚动数组也可以以0ms过掉.. 　　做这条题时很深刻地感受得到..这条题是斜着划分阶段的..太伟大了啦..而且由于每一阶段中..横坐标与纵坐标有一种莫名的内在关系..所以为数组节约了不少维..{不过就算不节约..N<=20..也应该不会超..}.. 用sum[k,x,y,z]表示当走到第K步时,且三人横坐标分别为X,Y,Z时..所取数的最大值..由于每一个人都可以由2个方向推来..所以一共有2^3=8种状态.. sum[k,x,y,x]=max(sum[k,x,y,z],sum[k-1,x+f[i,1],y+f[i,2],z+f[i,3]]) 且由于第K步只能到达横坐标<=min(k,n)的点..所以其实循环时可以节约节约.. 注意:每一格只能取一次..数组的大小.. 【代码】

#include 
#include 
#define max(a,b) a>b?a:b
int min(int a, int b)
{

       if (a < b)
              return a;
       else
              return b;

}

int f[41][21][21][21], a[21][21];

int main()
{

       int n, i , j, k, x1, x2, x3, temp, s1, s2, s3;
       scanf("%d", &n);

       for (i = 1; i <= n; i++)
       {
              for (j = 1; j <= n; j++)
                     scanf("%d", &a[i][j]);

       }

       memset(f, 0, sizeof(f));
       f[1][1][1][1] = a[1][1];

       for (k = 2; k <= n + n -1; k++)
       {
              for (x1 = 1; x1 <= min(k, n); x1++)
              {

                     for (x2 = 1; x2 <= min(k, n); x2++)
                     {
                            for (x3 = 1; x3 <= min(k, n); x3++)
                            {
                                   temp = a[k - x1 + 1][x1] + a[k - x2 + 1][x2] + a[k - x3 + 1][x3];

                                   if (x1 == x2)
                                          temp -= a[k - x1 + 1][x1];

                                   if (x1 == x3)
                                          temp -= a[k - x1 + 1][x1];

                                   if (x2 == x3)
                                          temp -= a[k - x2 + 1][x2];

                                   if (x1 == x2 && x1 == x3)
                                          temp += a[k - x1 + 1][x1];

                                   for (s1 = -1; s1 <= 0; s1++)
                                   {
                                          for (s2 = -1; s2 <= 0; s2++)
                                          {
                                                 for (s3 = -1; s3 <= 0; s3++)
                                                 {
                                                        f[k][x1][x2][x3] = max(f[k][x1][x2][x3], f[k - 1][x1 + s1][x2 + s2][x3 + s3] + temp);
                                                 }
                                          }
                                   }
                            }
                     }
              }
       }

       printf("%d\n", f[n + n - 1][n][n][n]);
       return 0;
}