11263: 【原1263】纸来纸去

题目描述

author: Jerry Wu 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1263

Description

晔神和纯哥是好基友，他们一刻不交谈就甚是想念对方。一节课上，班上同学被强制安排坐成一个m行n列的矩阵，而晔神被安排在左上角，坐标(1,1)；纯哥被安排在右下角，坐标(m,n)，因此，他们就无法直接交谈了。幸运的是，班上的热心同学们可以通过传纸条来帮助他们进行交流，但从晔神传到纯哥的纸条只可以向下或者向右传递，从纯哥传给晔神的纸条只可以向上或者向左传递，并且每位同学只能帮助他们传递一次。

除了每人只能帮忙一次之外，同学们的热心度也有不同，这关系到晔神和纯哥交谈的成功率！晔神和纯哥希望同学们帮他们一来一回传递两次纸条（即两条路径），并使得传递过程中同学们的热心程度之和最大。现在，请你帮助晔神和纯哥找到符合他们急迫心情的两条路径。

Input Format

输入的第一行有2个用空格隔开的整数m和n，表示同学们的座位有m行n列。

接下来的m行，每行有n个自然数，记作aij，表示第i行j列的学生的热心程度。每行数之间用空格隔开。（1<=aij<=100）

Output Format

输出为一个整数，表示一来一回过程中同学们的热心度之和的最大值。

Limits

30%的数据满足：1<=m,n<=10

100%的数据满足：1<=m,n<=50

Sample Input

Sample Output

Hint

两条路径同时进行

考虑到纸条所在位置的坐标与时间的关系，通过这个关系可以把4维数组压缩到3维

yyong119's solution

#include <iostream>
#include <algorithm>
using namespace std;

int m,n;
int map[55][55];
int dp[55][55][55];

int main(){

    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> map[i][j];
    dp[0][0][0] = map[0][0];

    for (int i = 1; i < n; ++i)
        dp[0][0][i] = dp[0][0][i - 1] + map[0][i];

    for (int i = 1; i < m; ++i) // 层数
        for (int pre_l = 0; pre_l < n - 1; ++pre_l) // 第一个位置
            for (int pre_r = pre_l + 1; pre_r < n; ++pre_r) { //第二个位置，两个上层位置
                int tmp = dp[i - 1][pre_l][pre_r];
                for (int cur_l = pre_l; cur_l < pre_r; ++cur_l) { //当前层左边点平移后位置
                    tmp += map[i][cur_l];
                    int t = tmp;
                    for (int cur_r = pre_r; cur_r < n; ++cur_r) { // 当前层右边点平移后位置
                        t += map[i][cur_r];
                        dp[i][cur_l][cur_r] = max(dp[i][cur_l][cur_r], t);
                    }
                }
            }
    cout << dp[m - 1][n - 2][n - 1] << endl;
    // cout << dp[1][1][2] << endl;
    // for (int i = 0; i < m; ++i) {
    //     for (int j = 0; j < n; ++j) {
    //         for (int k = 0; k < n; ++k)
    //             cout << dp[i][j][k] << " ";
    //         cout << endl;
    //     }
    //     cout << endl;

    // }
    return 0;
}