AcWing 275. 传纸条

标签：格式   ons   amp   its   max   std   const   路径   之间   

题目描述

给定一个 N*M 的矩阵A，每个格子中有一个整数。

现在需要找到两条从左上角 (1,1) 到右下角 (N,M) 的路径，路径上的每一步只能向右或向下走。

路径经过的格子中的数会被取走，两条路径可以经过同一个格子，但格子中的数 只能被取一次。

求取得的数之和最大是多少。

输入格式
第一行有2个用空格隔开的整数n和m，表示矩阵有n行m列。

接下来的n行是一个n*m的矩阵，每行的m个整数之间用空格隔开。

输出格式
输出一个整数，表示答案。

数据范围
1≤n,m≤50
输入样例：
3 3
0 3 9
2 8 5
5 7 0
输出样例：
34
---

思路如下:
假设dp[x1, y1, x2, y2]为[x1, y1]的一条路径的值
[x2, y2]为另一条路径的值
因为每条路径有两个状态
[x1, y1] [x1 - 1, y1] [x1, y1 - 1]
[x2, y2] [x2 - 1, y2] [x2, y2 - 1]
故有如下4个状态
[x1 - 1, y1, x2 - 1, y2]
[x1 - 1, y1, x2, y2 - 1]
[x1, y1 - 1, x2 - 1, y2]
[x1, y1 - 1, x2, y2 - 1]
初态
dp[0][0][0][0] = 0;
终态
dp[n][m][n][m];
如果到达的状态为dp[i][j][z][h] 如果i == z && j == h,那么会走过相同的通道，所以只能加一次
故转移状态为 dp[i][j][z][h] = max(dp[i][j][z][h], dp[i - 1][j][z - 1][h] + arr[i][j]);
dp[i][j][z][h] = max(dp[i][j][z][h], dp[i - 1][j][z][h - 1] + arr[i][j]);
dp[i][j][z][h] = max(dp[i][j][z][h], dp[i][j - 1][z - 1][h] + arr[i][j]);
dp[i][j][z][h] = max(dp[i][j][z][h], dp[i][j - 1][z][h - 1] + arr[i][j]);
如果步走过相同的通道,那么转移状态为
dp[i][j][z][h] = max(dp[i][j][z][h], dp[i - 1][j][z - 1][h] + arr[i][j] + arr[z][h]);
dp[i][j][z][h] = max(dp[i][j][z][h], dp[i - 1][j][z][h - 1] + arr[i][j] + arr[z][h]);
dp[i][j][z][h] = max(dp[i][j][z][h], dp[i][j - 1][z - 1][h] + arr[i][j] + arr[z][h]);
dp[i][j][z][h] = max(dp[i][j][z][h], dp[i][j - 1][z][h - 1] + arr[i][j] + arr[z][h]);
---
代码如下:

#include 
using namespace std;
const int MAXN = 55;
int arr[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
int n, m;
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i 

AcWing 275. 传纸条

标签：格式   ons   amp   its   max   std   const   路径   之间   

原文地址：https://www.cnblogs.com/qq136155330/p/10865421.html