传纸条 https://www.acwing.com/problem/content/277/
NOIP2008提高组,Google面试题

给定n*m的矩阵，每个格子有对应权值
从左上角起点，只能向下和向右，走到右下角终点
一共走两次，每个格子只能走一次
求经过的格子的权值之和的最大值

状态表示：

走两遍看成同时走
1.集合 - f[k, x1, x2] 所有第一条路线走到(x1,k-x1)第二条路线走到(x2,k-x2)的集合
        k表示横纵坐标之和，用k-x表示y，若x1=x2，则两坐标重合
2.属性 - Max

状态计算：

t = w[x1][y1]
if ( x1 != x2 ) t += w[x2][y2]  两点重合

1.右 右 f[k][x1][x2] = f[k - 1][x1][x2] + t
2.右 下 f[k][x1][x2] = f[k - 1][x1][x2 - 1] + t
3.下 右 f[k][x1][x2] = f[k - 1][x1 - 1][x2] + t
4.下 下 f[k][x1][x2] = f[k - 1][x1 - 1][x2 - 1] + t

x的范围
1 <= x <= n
1 <= x - k <= m
-> k - m <= x <= k - 1 
-> max(1, k - m) <= x <= min(k - 1, n)

时间复杂度 o(n^3)

#include <iostream>
using namespace std;

const int N = 52;
int f[N * 2][N][N], w[N][N];
int m, n;

int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= m; j ++ )
            cin >> w[i][j];
    for ( int k = 2; k <= m + n; k ++ )
        for ( int x1 = max(1, k - m); x1 <= min(k - 1, n); x1 ++ )
            for ( int x2 = max(1, k - m); x2 <= min(k - 1, n); x2 ++ )
                for ( int a = 0; a <= 1; a ++ )     //用循环表示以上四种情况
                    for ( int b = 0; b <= 1; b ++ )
                        if ( x1 != x2 || k == 2 || n + m == k ) //看成一起走，不能有重合的情况
                        {
                            int t = w[x1][k - x1] + w[x2][k - x2];  
                            f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + t);
                        }
    cout << f[n + m][n][n] << endl;
    return 0;
}