传纸条

标签：路径 cn 四维 int MAX 纸条

P1006 [NOIP2008 提高组] 传纸条 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 四维dp
• 一二维代表去的路径的坐标值，三四维代表回来时的路径（求解时也按去的方向求）取得的最大值
• 由于不能重合所以需要去重，所以在确定一条路径（一二维）后迭代三四维的时候只需要取原路径左下（或者右上的区域）
• 由于第三步的处理方法最后不可能重合，所以答案就是矩阵右下角也就是终点的上方和左边对应的点

#include <bits/stdc++.h>
using namespace std;
#define MAX 55
int dp[MAX][MAX][MAX][MAX];
int datas[MAX][MAX];
int n, m;
// https://www.luogu.com.cn/problem/P1006
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &datas[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int p = i + 1; p <= n; p++)
                for (int q = 1; q <= j - 1; q++)
                    dp[i][j][p][q] = max(dp[i - 1][j][p - 1][q], max(dp[i - 1][j][p][q - 1], max(dp[i][j - 1][p - 1][q], dp[i][j - 1][p][q - 1]))) + datas[i][j] + datas[p][q];
    printf("%d", dp[n - 1][m][n][m - 1]);
}

 

标签：路径,cn,四维,int,MAX,纸条
From： https://www.cnblogs.com/Wang-Xianyi/p/16625643.html