洛谷P1005 [NOIP2007 提高组] 矩阵取数游戏

题目描述

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

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

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

输入格式

输入文件包括 n+1 行：

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

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

输出格式

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

输入输出样例

输入 #1

2 3
1 2 3
3 4 2

输出 #1

82

说明/提示

NOIP 2007 提高第三题。

数据范围：

60% 的数据满足：1≤n,m≤30，答案不超过$10^{16}$。
100% 的数据满足：1≤n,m≤80
0≤ai,j≤10000

思路：
每行分别处理

对于每一行：每次取完剩余的一定是一个连续数组。

$dp[i][j]$记录的就是这个连续数组的状态，i是起点，j是终点

#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
long long matrix[85][85];
int m, n;
long long dp[85][85];

int input() {
    scanf_s("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf_s("%lld", &matrix[i][j]);
        }
    }
    return 0;
}
long long solve_for_row(int row) {//处理第row行

    /*
    dp[i][j]表示剩余元素为下标从i到j
    */
    if (m == 1) return matrix[row][1]*2;

    for (int i = 1; i < m; ++i) {//取第i个数字
        dp[1][m-i] = dp[1][m-i+1] + (matrix[row][m-i+1] << i);
        dp[i+1][m] = dp[i][m] + (matrix[row][i] << i);
        for (int t = 1; t < i; ++t)//左边取了t个数字,右边取了i-t个
        {
            dp[t+1][m-i+t] = max(dp[t][m-i+t] + (matrix[row][t]<<i), dp[t+1][m-i+t+1] + (matrix[row][m-i+t+1]<<i));
        }
    }
    long long ans = dp[1][1] + (matrix[row][1] << m);
    for (int i = 2; i <= m; ++i) {
        long long tmp = dp[i][i] + (matrix[row][i] << m);
        if (tmp > ans) ans = tmp;
    }
    return ans;    
}

int main() {
    input();
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += solve_for_row(i);
    }
    printf("%lld", ans);
    return 0;
}

这个解法只能得到60分。
因为答案还需要高精。longlong是会溢出的。
但是….我真的不想写高精了。。

附上一开始的错误解法:

#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

long long matrix[85][85];
int m, n;
long long dp[85][85][2];

int input() {
    scanf_s("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf_s("%lld", &matrix[i][j]);
        }
    }
    return 0;
}
long long solve_for_row(int row) {//处理第row行
    if (m == 1) return matrix[row][1]*2;
    //矩阵需要存储:第row行第i(1~m)个数在第j(1~m)次从k(1/0,1为左,0为右)取的最大值
    memset(dp, -1, 85 * 85 * 2 * 4);
    dp[1][1][1] = matrix[row][1]*2;
    dp[m][1][0] = matrix[row][m]*2;
    for (int j = 2; j <= m; ++j) {
        for (int i = 1; i <= m; ++i) {
            if (dp[i - 1][j - 1][1] != -1) {
                dp[i][j][1] = (matrix[row][i]<<j) + dp[i - 1][j - 1][1];
            }
            if (dp[i + 1][j - 1][0] != -1) {
                dp[i][j][0] = (matrix[row][i] << j) + dp[i + 1][j - 1][0];
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= m; ++i) {
        if (dp[i][m][0] > ans) ans = dp[i][m][0];
        if (dp[i][m][1] > ans) ans = dp[i][m][1];
    }
    return ans;
}

int main() {
    input();
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += solve_for_row(i);
    }
    printf("%lld", ans);
    return 0;
}