题目描述

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n×m 的矩阵，矩阵中的每个元素 ai,j​ 均为非负整数。游戏规则如下：

1. 每次取数时须从每行各取走一个元素，共 n 个。经过 m 次后取完矩阵内所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 ×2i，其中 i 表示第 i 次取数（从 1 开始编号）；
4. 游戏结束总得分为 m 次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入格式

输入文件包括 n+1 行：

第一行为两个用空格隔开的整数 n 和 m。

第 2∼n+1 行为 n×m 矩阵，其中每行有 m 个用单个空格隔开的非负整数。

输出格式

输出文件仅包含 1 行，为一个整数，即输入矩阵取数后的最大得分。

输入输出样例

输入 

2 3
1 2 3
3 4 2

输出

82

说明/提示

【数据范围】

对于 60% 的数据，满足 1≤n,m≤30，答案不超过 1016。
对于 100% 的数据，满足 1≤n,m≤80，0≤ai,j​≤1000。

矩阵取数游戏解析与解法介绍

题目背景

这是一个经典的动态规划问题，要求从一个给定的 n×m 矩阵中每次从每行各取走一个元素（只能从行首或行尾取），经过 m 次后取完矩阵内所有元素，并计算每次取数的得分。每次取数的得分等于被取走的元素值乘以 2^i，其中 i 表示第 i 次取数（从 1 开始编号）。最终求出取数后的最大得分。

输入输出格式

• 输入：
  • 第一行为两个用空格隔开的整数 n 和 m，分别表示矩阵的行数和列数。
  • 接下来的 n 行为 n×m 的矩阵，每行有 m 个用单个空格隔开的非负整数。
• 输出：
  • 仅包含一行，为一个整数，即输入矩阵取数后的最大得分。

样例分析

对于给定的样例：

2 3
1 2 3
3 4 2

我们需要构造出一个 2×3 的矩阵，并根据规则计算每次取数的最大得分。

解题思路

为了求解这个问题，我们可以使用动态规划的方法。具体步骤如下：

1. 定义状态：设 dp[i][j] 表示当前已经取了 i 次数，且第 k 行已经取走了前 j 或后 m-j 个元素时的最大得分。
2. 状态转移方程：
   • 对于每个状态 (i, j)，我们需要考虑从每行的行首或行尾取数的情况。
   • 如果从行首取，则得分增加 matrix[k][j] * 2^i；如果从行尾取，则得分增加 matrix[k][m-j-1] * 2^i。
3. 边界条件：初始状态为 dp[0][0] = 0，表示还没有取数时得分为 0。
4. 最终结果：dp[m][j] 中的最大值即为所求的最大得分。

由于直接使用四维数组会导致内存和时间复杂度过高，我们可以通过逐行处理的方式将问题简化为二维动态规划。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 80;
const int MAX_M = 80;
typedef long long ll;

int n, m;
vector<vector<int>> matrix(MAX_N, vector<int>(MAX_M));
vector<vector<ll>> dp(2, vector<ll>(MAX_M + 1, 0));

void readMatrix() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }
}

ll maxScore() {
    const ll BASE = 2;
    ll score = 0;
    for (int k = 0; k < m; ++k) {  // 第k次取数
        ll pow2k = 1LL << k;  // 计算2^k
        fill(dp[0].begin(), dp[0].end(), 0);
        fill(dp[1].begin(), dp[1].end(), 0);

        for (int i = 0; i < n; ++i) {  // 遍历每一行
            for (int j = 0; j <= k + 1 && j <= m; ++j) {  // j表示从行首取的数量
                if (j > 0) {
                    dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - 1] + static_cast<ll>(matrix[i][j - 1]) * pow2k);
                }
                if (j <= k) {
                    dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j] + static_cast<ll>(matrix[i][m - k + j - 1]) * pow2k);
                }
            }
        }

        for (int j = 0; j <= k + 1 && j <= m; ++j) {
            score += dp[(n - 1) % 2][j];
        }
    }

    return score;
}

int main() {
    readMatrix();
    cout << maxScore() << endl;
    return 0;
}

详细解释

1. 读取矩阵：

   • 使用 readMatrix 函数读取输入数据并填充 matrix 数组。

2. 动态规划核心逻辑：

   • dp[2][MAX_M + 1] 数组用于存储动态规划的状态，其中 dp[0] 和 dp[1] 分别存储两轮交替使用的状态。
   • pow2k 用于存储 2^k，表示第 k 次取数的权重。
   • 对于每个取数次数 k，遍历每一行，计算从行首或行尾取数的最大得分，并更新 dp 数组。

3. 状态转移方程：

   • 对于每个状态 (i, j)，我们需要考虑两种情况：
     • 从行首取数：dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - 1] + matrix[i][j - 1] * pow2k)
     • 从行尾取数：dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j] + matrix[i][m - k + j - 1] * pow2k)

4. 输出结果：

   • 最终的结果是 dp 数组中所有可能状态的最大值之和。

时间复杂度分析

• 动态规划的时间复杂度为 O(n * m^2)，因为我们需要遍历每个取数次数 k，并对每行进行两次取数操作（行首和行尾）。
• 由于 n 和 m 的最大值为 80，这个复杂度在实际运行中是可以接受的。