方格取数

题意

这是基于数字dp的基础上的一道题，有一个方格，里面有数，我们需要走两遍，只能走下或者走右，不能回头，走到右下角结束，第一遍走过的格子里的数清0，第二遍就再经过就是0了，求两次过后得到的最大数和。

2.gif

分析

dp是完美利用了集合的思想，解决这类问题的朴素思想是枚举，可是枚举每种情况的时间复杂度是非常恐怖的，往往是指数级别的，这时候我们就利用集合的思想，把相同情况的划分为一个集合里(这里是不是巧妙的运用到了拓扑序的思路)，然后把集合从小到大递推下去，求出最佳值。（阅读理解好题目的边界和条件）

  • 状态表示
  • 状态集合划分

状态表示分为两步，确定状态定义式，明确状态属性（意义）。

集合划分的要求：

  • 不重复（理论看情况，求max和min时可以重复）
  • 不漏

然后根据集合的划分来求出状态转移方程，一般用拓扑序的思路来求

拓扑序也就是事件发生的前后次序问题，只有前提条件发生了，它才会发成，从集合论来说，从小集合来推出大集合，这个顺序不能乱。

接下来回归到这个题目：

我们先确定状态表示，我们让两次同时进行，这样能够解决不能重复选择这个问题，这时候我们朴素的状态表示是：

\[f(x_1,y_!,x_2,y_2,k)\]

状态属性是从 $(1,1)(1,1)$ 到 $(x1,y1)(x2,y2)$ 的最大数和，k则代表是不是重复选择了

这样是五维，天哪，有点大了这个数组，我们有没有什么办法去优化呢？答案是有的。

我们可以观察，每次都是两个路线都是走1步，它们的x,y相加肯定一致，推出数学公式

\[x_1 + y_1 = x_2 + y_2 = k\]

k初始是2，因为刚开始坐标数相加就是2，之后这两条路线同时走一步，k就加1.

我们发现 $k$ 可以代替 $x_1,x_2$ 或者 $y_1, y_2$, 得出最后的状态表示

\[f(k,x_1,x_2)\]

现在我们来划分状态：

第一条路线有两种移动情况，第二条也是一样，$2*2 = 4$ 我们可以分为 4 种情况。

  1. 下下
  2. 下右
  3. 右右
  4. 右下

好了分析完毕，开始代码实现。

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int w[N][N];
int f[2 * N][N][N];

int main()
{
    int n;
    scanf("%d", &n);
    
    int a, b, c;
    while (cin >> a >> b >> c, a || b || c) w[a][b] = c;
    
    for (int k = 2; k <= 2 * 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 (j1 != j2) t += w[i2][j2];
                    int &x = f[k][i1][i2];
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2] + t);
                    x = max(x, f[k - 1][i1][i2 - 1] + t);
                }
            }
        }
    }
    printf("%d\n", f[2 * n][n][n]);
    return 0;
}