[题解][生贺]洛谷P1005-矩阵取数游戏

[题解][生贺]洛谷P1005-矩阵取数游戏

主要思路构建: 2025.3.3

最终攻破:2025.3.3

文章撰写:2025.3.3 - 2025.3.4

感谢朋友的生日礼物，如封面图所示，miku可爱捏，晕晕晕。

为了庆祝生日，写了这篇题解，预期于生日当天发布(3.5)。

可惜3月3号爆发感冒，不知道生日那天会不会好~(QAQ)。

P1005 矩阵取数游戏 这道题是我在大一上时遇见的，初次想用贪心，发现贪心走不通，后面看到标签有动态规划，感觉这十分高级，浅浅了解到了各种算法。如今约一年后的大二下终于做出来了。这道题算是我故意留到生日前夕做的（尽管对是否能做出来没底）。动态规划我并没有系统性地学习，我对题目的态度是“靠自己“全力尽力做出来，之前只做出来几道一维dp，于思路构建时才发现这可能是二维dp，我很高兴凭着自己一步一步地推理得到了正确答案。另外这道题还需要高精度，我拿之前写过的凑上，测试点过不了，后来发现是max函数未重构以及对0这个特殊数字没有进行特殊处理导致的。总归言之，可喜可贺，可喜可贺。

题目

[P1005 NOIP 2007 提高组] 矩阵取数游戏 - 洛谷

P1005 [NOIP 2007 提高组] 矩阵取数游戏

题目描述

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

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

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

输入格式

输入文件包括 \(n+1\) 行：

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

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
2 3
1 2 3
3 4 2

输出 #1

1
82

说明/提示

【数据范围】

对于 \(60\%\) 的数据，满足 \(1\le n,m\le 30\)，答案不超过 \(10^{16}\)。
对于 \(100\%\) 的数据，满足 \(1\le n,m\le 80\)，\(0\le a_{i,j}\le1000\)。

【题目来源】

NOIP 2007 提高第三题。

初步思路

对于这个矩阵取数游戏而言，我们想要取得矩阵的最大得分，其实就是取得矩阵中每一行的最大得分，我们设置这个求解函数为FUN(int a[], int low, int high), 我们可以很轻松地得到完成任务的递归函数(尽管它在问题规模很大时，时间效率低)：

Fun(a,low,high) = 2*max(a[low]+Fun(a,low+1,high),a[high]+Fun(a,low,high-1))

代码如下:

1
2
3
4
5
6
7
8
9
int Fun(int a[],int low, int high){
	if(low == high) return 2*a[low];
	else if(low < high){
		return 2*max(a[low]+Fun(a,low+1,high),a[high]+Fun(a,low,high-1));
	}
	else{
		return -1;
	}
}

显然，这样的代码无法满足测试点的需求，他的时间复杂度是指数级的。 我们不禁思考，这样的递归运算中存在大量的重复运算吗？ 是的！ 例如，对于Fun(a,0,0)，有Fun(a,1,0)和Fun(a,0,1)都调用了，并且它们自身也被重复调用了！ 接下来，我们的尝试是，动态规划算法。

主要思路（状态转移方程的构建）

设置dp[n][n],其中 一维为high, 二维为low. 设它们分别为i、j 我们得到状态转移方程如下:

dp[i][j] = 2*max(a[i]+dp[i+1][j],a[j]+dp[i][j-1])

同时，对于dp[i][i],dp[i][i] = a[i] 并且，j一定大于等于i（low不能高于high） 我们知道了循环起点一定和已知的dp[i][i]有关,而循环的终点应该是dp[0][n-1]。

也就是说，对这个矩阵而言，我们已知正对角线的元素，所求为上三角顶点元素，我们根据动态转移方程，不妨知道dp[i][j]取决于左和下的值,于是loop应该是自上向右的，也就是 i=n-1,且i++ ; j=i 且 j++, 这是一个螺旋上升的过程，i从n-1开始，使得dp[i][j]求解得到了dp[i+1][j]的一个前提，之后j再从i开始向右，使dp[i][j]也有了另一个前提dp[i][j-1]。当然，我这套做法是先满足下再满足左，亦可以是先满足左再满足下，只不过此时嵌套循环的次序要发生改变罢了。

于是我们得到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long Fun(long long a[],int n){
	long long dp[n][n];
	for(int i=n-1; i>=0; i--){
		for(int j=i; j < n; j++){
			if(j != i){
				dp[i][j] =  2*max(a[i]+dp[i+1][j],a[j]+dp[i][j-1]);
			}
			else{
				dp[i][j] = 2*a[i];
			}
		}
	}
	return dp[0][n-1];
}

最终代码（long long不够满足测试集）

使用了自己写的高精度,这里使用的是string类型，其实使用vector<int>也可以。

当然还有c++自带的__int128_t，我还不会用( )

(重构了max函数，由于忘记了这一点走了弯路，因为字符串的比较是字典序而非数值大小)

最终代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
using namespace std;

string operator+(string a, string b){
    int c=0;
    int posa = a.length()-1;
    int posb = b.length()-1;
    string res;
    if(a == "0") return b;
    if(b == "0") return a;
    while(posa >= 0 || posb>=0){
        int tema = 0;
        int temb =0;
        if(posa>=0)
        tema = (int)(a[posa]-'0');
        if(posb>=0)
        temb = (int)(b[posb]-'0');
        int temp = tema + temb + c;
        c = temp/10;
        temp %= 10;
        res = (char)(temp+'0')+ res;
        posa--;
        posb--;
    }
    if(c!=0){
        res = (char)(c+'0') + res;
    }
    return res;
}

string operator*(string a, string b){
    int i = 0;
    int posa = a.length()-1;
    int posb = b.length()-1;
    if(b.length() > a.length()){
        string temp = a;
        a = b;
        b = temp;
    }
    string res;
    if(a=="0" || b=="0") return "0";
    while(posb>=0){
        int c = 0;
        int temp = (int)(b[posb] - '0');
        string cell;
        if(temp!=0)
        while(posa>=0){
            int t = (int)(a[posa] - '0') * temp + c;
            c = t /10;
            t %= 10;
            cell = (char)(t+'0') + cell;
            posa--;
        }
        if(c!=0) cell = (char)(c+'0')+ cell;
        for(int i=1; i<b.length()-posb && cell!="0"; i++) cell = cell+'0';
        res = res+cell;
        posa = a.length()-1;
        posb --;
    }
    return res;
}

string max(string a,string b){
    if(a.length() == b.length()){
        if(a>b) return a;
        else return b;
    }
    else if(a.length() > b.length()) return a;
    else return b;
}


string Fun(string a[],int n){
	string dp[n][n];
	for(int i=n-1; i>=0; i--){
		for(int j=i; j < n; j++){
			if(j != i){
				dp[i][j] = max(a[i]+dp[i+1][j],a[j]+dp[i][j-1])* "2";
			}
			else{
				dp[i][j] = a[i]*"2";
			}
		}
	}
	return dp[0][n-1];
}

int main(){
    int n,m;
    cin >> n >> m;
    string a[n][m];
    string total = "0";
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> a[i][j];
        }
        total = Fun(a[i],m)+total;
    }
    cout << total;
}