$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题是 AcWing 1015.摘花生 的变式，只不过原题是走一次，这道题是走两次

考虑原题的 $f[i][j]$ 的定义——从 $(1,\ 1)$ 到 $f[i,\ j]$ 的所有路径当中的最大值，本题也可以定义成：从 $(1,\ 1),\ (1,\ 1)$ 到 $f[i1,\ j1],\ f[i2,\ j2]$ 的所有路径当中的最大值，即状态表示为：$f[i1][j1][i2][j2]$

本题是走两次，但同一个数只能取一次，由于我们最终是取两次路径的总和，因此这一个数加在哪条路径都是允许的

当两条路径第一次重合时，显然有：$i1\ =\ i2,\ j1\ =\ j2$ ，此条件为充要条件

其实本题考虑到这里就可以下手做了，但还有状态优化的空间

如果我们考虑将四维下降到三维的话，我们需要找到 $i1,\ j1$ 和 $i2,\ j2$ 之间的关系，也就是需要找出在两条路线第一次到达同一个格子的时候的关系

我们知道当两条线路第一次重合时，有：$i1\ =\ i2,\ j1\ =\ j2$，基于此，我们可以推出：$i1\ +\ j1\ =\ i2\ +\ j2$

也就是说，当满足 $i1\ +\ j1\ =\ i2\ +\ j2$ 时，两条路线可能重合，这仅仅是一个充分条件

我们设 $k\ =\ i1\ +\ j1\ =\ i2\ +\ j2$，这样我们便可以用 $k$ 来表示 $j1$ 和 $j2$ ，并且依旧可以用 $k$ 来进行重合的判断

此时 $f[k,\ i1,\ i2]$ 的定义为：从 $(1,\ 1),\ (1,\ 1)$ 到 $f[i1,\ j1],\ f[i2,\ j2]$ 的所有路径当中的最大值，其中 $k\ =\ i1\ +\ j1\ =\ i2\ +\ j2$

在集合的划分部分，由于有两条路线，因此会有四种走法：

1. 第一条下，第二条下：此时从 $(i1\ -\ 1,\ j1),\ (i2\ -\ 1,\ j2)$ 转移到 $(i1,\ j1),\ (i2,\ j2)$，即 $f[k\ -\ 1][i1\ -\ 1][i2\ -\ 1]$ 到 $f[k][i1][i2]$

2. 第一条下，第二条右：此时从 $(i1\ -\ 1,\ j1),\ (i2,\ j2\ -\ 1)$ 转移到 $(i1,\ j1),\ (i2,\ j2)$，即 $f[k\ -\ 1][i1\ -\ 1][i2]$ 到 $f[k][i1][i2]$

3. 第一条右，第二条下：此时从 $(i1,\ j1\ -\ 1),\ (i2\ -\ 1,\ j2)$ 转移到 $(i1,\ j1),\ (i2,\ j2)$，即 $f[k\ -\ 1][i1][i2\ -\ 1]$ 到 $f[k][i1][i2]$

4. 第一条右，第二条右：此时从 $(i1,\ j1\ -\ 1),\ (i2,\ j2\ -\ 1)$ 转移到 $(i1,\ j1),\ (i2,\ j2)$，即 $f[k\ -\ 1][i1][i2]$ 到 $f[k][i1][i2]$

有一个问题是：这里的 $k$ 是怎么算的？

很简单，因为 $k\ =\ i1\ +\ j1\ =\ i2\ +\ j2$ ，所以 $k\ -\ 1\ =\ i1\ +\ j1\ -\ 1=\ i2\ +\ j2\ -\ 1$ ，后面两个部分的减一可以作用在 $i$ 上，也可以作用在 $j$ 上

并且我们还可以得到一个结论是，$k$ 的初始值为 2 ，这是因为 $i1$ 和 $j1$ 的初始值均为 1 （这一点放在 $i2$ 和 $j2$ 上面同理）

当两条路线经过同一个格子时，这个格子的数只能被加一次，除此之外的情况我们需要加上 $w[i1][j1]$ 和 $w[i2][j2]$ ，之后对路径求最大值就可以了

完整代码如下：

#include <iostream>

using namespace std;

const int N = 15;
int w[N][N];
int f[N + N][N][N];//注意第一维是N + N
int n;

int main()
{
    cin >> n;
    int a, b, c;

    while(cin >> a >> b >> c, a || b || c) w[a][b] = c;

    for(int k = 2; k <= n + n; k++)
        for(int i1 = 1; i1 <= n; i1++)
            for(int i2 = 1; i2 <= n; i2++)
            {
                int j1 = k - i1, j2 = k- i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = w[i1][j1];
                    if(i1 != i2) t += w[i2][j2];//并不需要对j进行判断，因为j由k求得，而k是最外层循环，因此只要i不等j就不等
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t);//(i1-1, j1) (i2-1, j2)
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + t);//(i1-1, j1) (i2, j2 - 1)
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t);//(i1, j1 - 1) (i2 - 1, j2)
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + t);//(i1, j1 - 1) (i2, j2 - 1)
                }
            }
    cout << f[n + n][n][n] << endl;
    return 0;
}