题解 P1004 【方格取数】

Azuree · 2019-08-13 22:41:00 · 题解

一道典型的棋盘dp。
一共需要走两次，我们不妨同时处理这两条路径。这样，我们既可以方便地处理两条路径重合的情况，也可以减少代码的时间复杂度。
最朴素的想法是开一个四维数组f[x_1][y_1][x_2][y_2]表示当两条路径分别处理到(x_1,y_1)和(x_2,y_2)时能够获得的最大的累积和。但是，四维数组处理起来时间复杂度太大了，所以我们要想办法把它降成三维。
我们可以发现，每当我们走一步，那么x坐标和y坐标之间总会有一个数加1。所以，我们可以用k来表示x坐标和y坐标的和，从而通过y坐标来计算出x坐标。由于k对于两条同时处理的路径可以是公共的，所以我们可以用f[k][y_1][y_2]来表示当前状态。
特殊的，由于每一个方格的数只可以取一次，所以我们要判断i和j是否相当。
于是，我们就可以得到一个状态转移方程了：

我们可以来看一下我们到底是通过哪些状态转移到当前状态的：

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define qwq printf("qwq\n");

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,m,map[205][205],f[205][205][205],x,y,v;

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

int main()
{
    m = read();
    n = m;
    x = read(); y = read(); v = read();
    while(x > 0)
    {
        map[x][y] = v;
        x = read(); y = read(); v = read();
    }
    for(int k = 1; k <= m + n; k++)
        for(int i = 1; i <= min(k,n); i++)
            for(int j = 1; j <= min(k,n); j++)
            {
                f[k][i][j] = cmp(f[k - 1][i][j],f[k - 1][i - 1][j],f[k - 1][i][j - 1],f[k - 1][i - 1][j - 1]) + map[k - i + 1][i] + map[k - j + 1][j];
                if(i == j) f[k][i][j] -= map[k - i + 1][i];
            }

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