题解：P1006 [NOIP 2008 提高组] 传纸条

题目传送门

可在专栏中查看。

这是一道运用到了动态规划的题。

首先我们先来看一下样例，下面是示意图。

注：红色线表示纸条从小轩传到小渊的路径，橙色线表示纸条从小渊传到小轩的路径。

那么最后的结果就是 34。

如果我们用二维 DP，经过思考我们就会发现，这种方法不成立，所以我们就要用多维 DP 了。

我们希望两条路径都不重复，那么我们就可以看成有两条路径从 (m,n) 点出发，每一个时间单位走 1 个点，我们只要找到一条路，使得 2 条路经在相同时间内走的点不重复就可以了。

我们除了统计走的步数，还要统计当前这条路的末尾位置。

现在状态就出来了，那就是 f[i][x_1][x_2] 表示两条路径的长度均为 i，第一条路末尾在 x_1 行，第二条路末尾在 x_2 行，经过的权值之和的最大值。

我们再来看一下状态转移方程。

我们还要特判一下，如果 x_1 和 x_2 相等，就说明走的 2 条路有个点重合了，就进行下一次循环。

我们再说一下边界和初始化。 我们要把 f 数组全部设为 -1，然后把 f[2][1][1] 设成 0。

最后就是答案了。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n, m, a[105][105], f[205][105][105], cm[5];//数组开大点，不然会RE
int main()
{
    //输入数据
    cin >> m >> n;
    for (int i = 1;i <= m;i++)
    {
        for (int j = 1;j <= n;j++)
        {
            cin >> a[i][j];
        }
    }
    memset(f, -1, sizeof(f));
    f[2][1][1] = 0;
    for (int i = 3;i <= n + m - 1;i++)//枚举路径长度i
    {
        for (int j = 1;j <= n - 1;j++)//枚举x1
        {
            for (int k = j + 1;k <= n;k++)//枚举x2
            {
                cm[1] = f[i - 1][j][k];
                cm[2] = f[i - 1][j - 1][k];
                cm[3] = f[i - 1][j][k - 1];
                cm[4] = f[i - 1][j - 1][k - 1];
                sort(cm + 1, cm + 1 + 4, greater<int>());//求4种情况的最大值
                if (cm[1] == -1)//如果到不了那个点
                {
                    continue;
                }
                f[i][j][k] = cm[1] + a[i - j][j] + a[i - k][k];//把最大值加上第i步第一条路径所在格子权值和第i步第二条路径所在格子权值
            }
        }
    }
    cout << f[n + m - 1][n - 1][n];//输出答案
    return 0;//结束！
}

说明：此题解中有部分内容借鉴了聪明王必胜的题解。