• 错误思路: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;
}