题解 | #方格取数#

• 错误思路：dp+贪心 86%测试点（题解里也有大佬用这种写法wa了，对我自己来说就是初学dp总是想贪）
  因此谨记：求解 全局最优 不要用 局部最优 思路！！！！！！！！！！！
• 正确思路：四维dp
• 题目大意：n*n的地图上分布数字，从左上角走到右下角，走两趟，第一趟走过的地方变成0，求两次走完取到的总数字相加的最大值。
• 题目分析：先说一下错误思路吧，走两趟，第一趟取能取到的最大总和，想到花店橱窗那道题（我的博客里也有题解，不嫌弃蒟蒻的话可以去康康啦~~），倒推求路径，再走一趟。
  错误代码以及自己造的样例：

//错误代码！！！
//错误代码！！！
//错误代码！！！
//错误代码！！！
/*
    1 2 0 0 0
    4 0 0 0 0
    0 0 2 0 0
    1 0 2 0 0
    答案是： 12
    输出是： 11
    左下角的1被忽略了
*/
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 15;
LL v[N][N], dp[N][N], maxx = 0;

int main()
{
    int x, y, n;
    scanf("%d", &n);

    while(scanf("%d%d", &x, &y), x!= 0 && y != 0)
        scanf("%d", &v[x][y]);

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + v[i][j];

    maxx = dp[n][n];
    LL ans = dp[n][n];

    for(int i = n; i ; i--)
    for(int j = n; j ; j--)
    {
        if(dp[i][j] == maxx)   //倒推寻找第一趟路径置零
            maxx -= v[i][j], v[i][j] = 0;
    }

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + v[i][j];

    ans += dp[n][n];
    printf("%lld", ans);

    return 0;
}

正确思路：假设两个人同时走，dp[ i ] [ j ] [ x ] [ y ] 表示第一个人走到（i, j）同时第二个人走到（x，y）所获得的最大值；

如图，甲走到C乙走到Z的情况有四种，即（A -> C && X -> Z ）、（A -> C && Y -> Z）、（B -> C && X -> Z ）、（B -> C && Y -> Z）
因此转移方程：
dp[i][j][x][y] = max（dp[i - 1][j][x - 1][ y ] , dp[i - 1][ j ][ x ][ y-1 ] , dp[ i ] [j - 1][x - 1][ y ] , dp[ i ][j - 1][ x ][y - 1]）
正确代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 15;
int v[N][N], dp[N][N][N][N], maxx = 0;

int main()
{
    int x, y, n;
    scanf("%d", &n);

    while(scanf("%d%d", &x, &y), x!= 0 && y != 0)
        scanf("%d", &v[x][y]);

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    for(int x = 1; x <= n; x++)
    for(int y = 1; y <= n; y++)
    {
        dp[i][j][x][y] = max(
            max( dp[i - 1][j][x - 1][ y ] , dp[i - 1][j][x][ y-1 ]),
            max( dp[i][j - 1][x - 1][ y ] , dp[i][j - 1][x][y - 1]));
        if(i == x && j == y)dp[i][j][x][y] += v[i][j];
        else dp[i][j][x][y] += v[i][j] + v[x][y]; //如果走到的是同一个点，只加一次，否则加两个点
    }

    printf("%d", dp[n][n][n][n]);
    return 0;
}