国网北京电力建设研究院网站,企业网站总承包建设模式关键步骤,广州网站建设在线,杭州网站提升排名矩阵取数游戏
题目描述
帅帅经常跟同学玩一个矩阵取数游戏#xff1a;对于一个给定的n行*m列的矩阵#xff0c;矩阵中的每个元素aij均为非负整数。游戏规则如下#xff1a; 1. 每次取数时须从每行各取走一个元素#xff0c;共n个。m次后取完矩阵所有的元素#xff1b; 2…矩阵取数游戏
题目描述
帅帅经常跟同学玩一个矩阵取数游戏对于一个给定的n行*m列的矩阵矩阵中的每个元素aij均为非负整数。游戏规则如下 1. 每次取数时须从每行各取走一个元素共n个。m次后取完矩阵所有的元素 2. 每次取走的各个元素只能是该元素所在行的行首或行尾 3. 每次取数都有一个得分值为每行取数的得分之和每行取数的得分 被取走的元素值*i其中i表示第i次取数从1开始编号 4. 游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序对于任意矩阵可以求出取数后的最大得分。
关于输入
包括n1行 第一行为两个用空格隔开的整数n和m。 第2~n1行为n*m矩阵其中每行有m个用单个空格隔开 lnm801aij1000
关于输出
仅包含1行为一个整数即输入矩阵取数后的最大的分。
例子输入
2 3
1 2 3
3 4 2例子输出
34
解题分析
这个问题的具体描述是给定一个n行m列的矩阵每次从每行中取走一个元素只能是行首或行尾的元素每次取数都有一个得分值为每行取数的得分之和每行取数的得分 被取走的元素值*i其中i表示第i次取数。求取数后的最大得分。
程序的主要思路如下
1. 首先程序读取两个整数n和m然后读取n行m列的矩阵存储在数组a中。
2. 然后程序对每一行进行处理。对于每一行程序初始化一个二维数组dpdp[i][j]表示从第i个元素到第j个元素包括i和j的子数组中取数的最大得分。
3. 程序遍历所有可能的子数组长度从1到m。对于每一个子数组长度程序遍历所有可能的子数组的起始位置。 - 如果子数组长度为1那么dp[i][j]就等于m * a[row][i]因为子数组只有一个元素所以取数的得分就是m * a[row][i]。 - 如果子数组长度大于1那么dp[i][j]就等于dp[i1][j] (m-len1) * a[row][i]和dp[i][j-1] (m-len1) * a[row][j]中的较大值。这是因为我们可以选择取第i个元素或者第j个元素所以我们需要比较这两种选择的得分取较大的那个。
4. 对于每一行dp[0][m-1]就是这一行的最大得分。程序将所有行的最大得分累加起来就得到了总的最大得分。
这个程序的时间复杂度是O(n*m^2)因为它需要对每一行遍历所有可能的子数组。如果矩阵的大小非常大那么这个程序可能会运行得比较慢。
代码实现
#include iostream
#include cstring
using namespace std;int dp[85][85];
int a[85][85];int main() {int n,m; cinnm;int ans0;for(int i0;in;i)for(int j0;jm;j){cina[i][j];}for(int row0;rown;row){memset(dp,0,sizeof(dp));for(int len1;lenm;len)for(int i0;im ilen-1m;i){int jilen-1;if(len1){dp[i][j]m*a[row][i];}else{dp[i][j]max(dp[i1][j](m-len1)*a[row][i],dp[i][j-1](m-len1)*a[row][j]);}}ansdp[0][m-1];}coutansendl;return 0;
}当然使用记忆搜索法也不错
这个程序是用来解决“矩阵取数游戏”问题的改进版本。它仍然使用了动态规划的思想但是采用了记忆化搜索的方法将递归的过程中重复的子问题的解存储起来避免了重复计算从而提高了效率。
程序的主要思路如下
1. 首先程序读取两个整数n和m然后读取n行m列的矩阵存储在数组a中。
2. 然后程序对每一行进行处理。对于每一行程序使用一个记忆化搜索的函数f(i, j)来计算从第i个元素到第j个元素包括i和j的子数组中取数的最大得分。
3. 函数f(i, j)的定义如下 - 如果dp[i][j]已经计算过那么直接返回dp[i][j]的值。 - 如果i等于j那么dp[i][j]就等于m * a[row][i]因为子数组只有一个元素所以取数的得分就是m * a[row][i]。 - 如果i不等于j那么dp[i][j]就等于f(i1, j) (m-ji) * a[row][i]和f(i, j-1) (m-ji) * a[row][j]中的较大值。这是因为我们可以选择取第i个元素或者第j个元素所以我们需要比较这两种选择的得分取较大的那个。
4. 对于每一行f(0, m-1)就是这一行的最大得分。程序将所有行的最大得分累加起来就得到了总的最大得分。
这个程序的时间复杂度是O(n*m^2)因为它需要对每一行遍历所有可能的子数组。如果矩阵的大小非常大那么这个程序可能会运行得比较慢。
注意这个程序假设输入的矩阵的行数和列数不超过80如果实际问题中矩阵的行数或列数可能超过这个值那么需要相应地调整数组的大小。
代码实现2
#include iostream
#include cstring
using namespace std;int dp[85][85];
int a[85][85];
int n,m,row;int f(int i,int j){if(dp[i][j]){return dp[i][j];}if(ij){return dp[i][j]a[row][i]*m;}else{return dp[i][j]max(f(i1,j)(m-ji)*a[row][i],f(i,j-1)(m-ji)*a[row][j]);}
}int main() {cinnm;int ans0;for(int i0;in;i)for(int j0;jm;j){cina[i][j];}for(row0;rown;row){memset(dp,0,sizeof(dp));ansf(0,m-1);}coutansendl;return 0;
}
