dp 分析

• 状态表示
  • 集合：所有…的集合
    • 条件：边界、前几个、后几个、体积小于…、时间小于…等（集合的设计带来的一些边界条件）
  • 属性：max、min ......（状态表示了这个集合的什么值？与状态转移相区别）
• 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。

两个性质

1. 两次传纸条，一定有一条在上面，另一条再下面。任何不满足的两条路径都可以从交点开始，之后的路径互换来实现一条在上面、另一条在下面。
2. 任何有交点的一上一下的两条路径，都可以变成两条完全不相交的路径。即至少有一条路径可以在交点附近（在上面的路径找交点上面的点，在下面的路径找交点下面的点），使得交点变为不相交。即一条不合法的路径，变为合法的路径。

1. 暴力解法

遍历每一种可能的两条路径，计算其每一个结果会导致超时。

考虑只走一次时，所有可能构成的状态空间：从（1，1）走到（50，50），路径总数等于从98步中选择49步向下（或向右）的组合数，$C^{49}_{98} = \frac{98!}{49! \times 49!}$，约为 $5.02 \times 10^{29}$。

显然走两次一定会超时。

2. 压缩状态空间 -> 简化题目， 约为 $10^{6}$

2.1 一维 dp 的思路解题

一维的简化做法，即 f[x][y] 表示到达 (x, y) 点时，能获取的最大值。

考虑用一维 dp 的思路解题，利用上述性质，可以转化为求f[x1][y1][x2][y2] ，表示两条路径分别到达 (x1, y1)、(x2, y2) 点时的最大值。$50^4$,约为 $10^6$，但数据量增大就不行了。

2.2 题干条件->状态压缩

由于题目可转化为，同时沿着两条路径走，路径没有交点，两条路径的最大和。因此横纵坐标之和始终相等，对不相等的情况进行计算是没有意义的，可以简化。

横纵坐标之和为 k，第一条路径横坐标为 x1，第二条路径横坐标为 x2，构造状态f[k][x1][x2] 表示第一条路径到达 (x1, k - x1)，第二条路径到达 (x2, k - x2) 时，路径和的最大值。

由状态的定义可知，k 一定，x1 = x2 时，状态是无效的，因为这意味着两条路径到达了交点。但是到达这个状态的最大值是可以计算的，即所有上一步状态里面的最大值。

计算每个状态值即可。最终的答案是计算 f[m + n][m][m] 的所有上一步状态的最大值。

2.2.1 计算每个状态的值。

int value = arc[x1][k - x1] + arc[x2][k - x2];

f[k][x1][x2] = max(res[k - 1][x1 - 1][x2 - 1], 
                res[k - 1][x1 - 1][x2], res[k - 1][x1][x2 - 1], 
                res[k - 1][x1][x2]) + value;

3. 待深入研究

k 取方格数

4. 代码

#include<iostream>
#include<cstdio>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 105;

int arc[N][N];
int res[N][N][N];

int get_max(int a, int b, int c, int d) {
    return max(max(a, b), max(c, d));
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;
    _rep_le(i, 1, m) {
        _rep_le(j, 1, n) {
            cin >> arc[i][j];
        }
    }

    // _rep_le(i, 1, m) {
    //     _rep_le(j, 1, n) {
    //         cout << arc[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    _rep_le(k, 2, m + n) {
        _rep_lt(x1, 1, min(m + 1, k)) {
            _rep_lt(x2, 1, min(m + 1, k)) {
                if (x1 == x2) continue;
                if ((k - x1 > n) || (k - x2 > n)) continue;
                int v = arc[x1][k - x1] + arc[x2][k - x2];
                res[k][x1][x2] = get_max(res[k - 1][x1 - 1][x2 - 1], 
                    res[k - 1][x1 - 1][x2], res[k - 1][x1][x2 - 1], 
                    res[k - 1][x1][x2]) + v;
                // cout << "k:" << k << "  x1:" << x1 << "  x2:" << x2 
                //     << "  res[" << k << "][" << x1 << "][" << x2 << "]:" << res[k][x1][x2] << endl;  
            }
        }
    }
    res[m + n][m][m] = get_max(res[m + n - 1][m - 1][m - 1], 
        res[m + n - 1][m - 1][m], res[m + n - 1][m][m - 1], 
        res[m + n - 1][m][m]);
    cout << res[m + n][m][m] << endl;
    return 0;
}