矩阵取数游戏（NOIP2007弱化版【动态规划不含高精度】）题目、分析及C++代码实现

原题再现¹

题目 - 矩阵取数游戏

描述

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

每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素；每次取走的各个元素只能是该元素所在行的行首或行尾；每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*i，其中i表示第i次取数（从1开始编号）；游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

关于输入

包括n+1行； 第一行为两个用空格隔开的整数n和m。 第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开 。

l<=n，m<=80，1<=aij<=1000

关于输出

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

例子输入

2 3

1 2 3

3 4 2

例子输出

34

基本分析

观察题目，易知对于每行而言任务相同，故问题可分割为对每行求出取数得分之和最大值并相加。

算法评析

对于每行取数得分最大值的求解有若干种方法，较容易想到的是贪心法与搜索法。

贪心法（Wrong Answer）

一般而言，观察题供测试数据，易得如下贪心方法：

贪心思想

每次取两端点中较小的一个数，加权求和。

错误原因

1、对于两端点相等的情况难以作出决断，取任意一个均有其合理性与不合理性； 2、看似符合排序不等式，实际上是以局部最优取代整体最优，错误判断结果，如果碰到较小数被较大数所夹的情况则易证其不是最优解。

搜索法(Time Out)

即每次对于取左端与右端进行搜索：

伪代码实现

int DFS(int l, int r, int depth) { //l,r为区间左右界,depth为搜索深度 if (depth == m) return a[l] * m; //到达深度后搜索中止 int x = a[l] * depth + DFS(l + 1, r, depth + 1);//取左端数 int y = a[r] * depth + DFS(l, r + 1, depth + 1);//取右端数 return max(x, y); //返回较大值 }

时间复杂度

O(n*2^m) 显然在数据较大时易超时。

动态规划

基本概念

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。 ²

关于本题

观察题目，易知对于每行而言任务相同，故问题可分割为对每行求出取数得分之和最大值并相加。对于每行均可验证其问题的阶段性及无后效性，并通过寻找局部最优解，通过动态规划以实现问题的高效求解。

阶段性

对于每一行而言，每一次取数均可视为一阶段，该阶段得分与且仅与上一行的取数结果及状态有关，满足阶段性。

无后效性

对于每一次取数，其所能达到的最优解仅与上一行的有限种状态和局部最优解有关。对于上一行的每一种状态，无论其取法顺序，最后剩余序列必然为连续若干数，取法顺序对于本行决策无影响，满足无后效性。

状态表示

以f[i][j]数组记录第i次取数后剩余区间左端为j时的最优解，“左端为j”即剩余区间为从j开始到m+j-i-1的连续m-i项。

例如

f[1][1]=a[m]表示第一次取数取右端时得分为a[m]，剩余项为1到m-1项； f[1][2]=a[1]表示第一次取数取左端时得分为a[1],剩余项为2到m项。

状态转移

每次比较取左侧端点与取右侧端点的得分大小，取较大解。

状态转移方程

f[i][j]=max{f[i-1][j-1]+a[j-1]*i,f[i-1][j]+a[j+m-i]*i}

伪代码实现

int f[200][200] = {0}; f[1][1] = a[m]; f[1][2] = a[1]; for (int i = 2; i <= m; i++) { for (int j = 1; j <= m; j++) { //出于安全起见对于第i-1行的数均判断其是否等于0 int x = (f[i - 1][j - 1] != 0) * (f[i - 1][j - 1] + a[j - 1] * i); int y = (f[i - 1][j] != 0) * (f[i - 1][j] + a[j + m - i] * i); f[i][j] = (x > y ? x : y); } } int max = 0; for (int i = 1; i <= m; i++) if (f[m][i] > max) max = f[m][i];

空间降维

观察到f[i][j]仅与f[i-1][j]和f[i-1][j-1]有关，故可调整j循环顺序，采用一维数组替代二维数组（尽管对这道题而言意义不大），则只需要一维数组f[j]即可。

状态转移方程（一维数组）

f[j]=max{f[j-1]+a[j-1]*i,f[j]+a[j+m-i]*i}

程序实现

最终程序代码（C++）如下：

程序代码³

#include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; int sum = 0; int a[200] = {0}; int f[200] = {0}; //基本定义信息 for (int k = 1; k <= n; k++) { for (int i = 1; i <= m; i++) cin >> a[i]; for (int i = 0; i <= m; i++) f[i] = 0; f[1] = a[m]; f[2] = a[1]; //DP初始化 for (int i = 2; i <= m; i++) for (int j = m; j >= 1; j--) { //出于安全起见对于第i-1行的数均判断其是否等于0 int x = (f[j - 1] != 0) * (f[j - 1] + i * a[j - 1]); int y = (f[j] != 0) * (f[j] + i * a[j + m - i]); f[j] = (x > y ? x : y); } int max = 0; for (int i = 1; i <= m; i++) if (f[i] > max) max = f[i]; sum += max; } cout << sum << endl; return 0; }

复杂度分析

时间复杂度

O(n*m²) 完全没有超时风险。

空间复杂度

二维数组O(m²) 一维数组O(m) 由此可见此处降维并不是必须的。

思考⁴

1、本题代码中对第i-1次取数得分是否为0的探讨是否必要？ 2、a[j+m-i]是否存在越界风险？ 3、本题中变量j的有效变化范围是多少？ 4、控制变量j的范围是否可以解决上述问题？

---

原题加强版可见 http://codevs.cn/problem/1166/ ↩︎

动态规划相关定义参照百度百科 https://baike.baidu.com/item/动态规划/529408?fr=aladdin ↩︎

在此去掉了绝大部分原有注释，请读者掌握算法原理后自行理解 ↩︎

欢迎评论或私信以交流意见，接受正当批评与指正 ↩︎