矩阵取数游戏
题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n行*m列的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*i，其中i表示第i次取数（从1开始编号）；
4. 游戏结束总得分为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
解题分析
这个问题的具体描述是：给定一个n行m列的矩阵，每次从每行中取走一个元素（只能是行首或行尾的元素），每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*i，其中i表示第i次取数。求取数后的最大得分。
程序的主要思路如下：
1. 首先，程序读取两个整数n和m，然后读取n行m列的矩阵，存储在数组`a`中。
2. 然后，程序对每一行进行处理。对于每一行，程序初始化一个二维数组`dp`，`dp[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[i+1][j] + (m-len+1) * a[row][i]`和`dp[i][j-1] + (m-len+1) * a[row][j]`中的较大值。这是因为，我们可以选择取第i个元素或者第j个元素，所以我们需要比较这两种选择的得分，取较大的那个。
4. 对于每一行，`dp[0][m-1]`就是这一行的最大得分。程序将所有行的最大得分累加起来，就得到了总的最大得分。
这个程序的时间复杂度是O(n*m^2)，因为它需要对每一行遍历所有可能的子数组。如果矩阵的大小非常大，那么这个程序可能会运行得比较慢。文章来源：https://www.toymoban.com/news/detail-759837.html
代码实现
#include <iostream>
#include <cstring>
using namespace std;
int dp[85][85];
int a[85][85];
int main() {
int n,m; cin>>n>>m;
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>a[i][j];
}
for(int row=0;row<n;row++){
memset(dp,0,sizeof(dp));
for(int len=1;len<=m;len++)
for(int i=0;i<m && i+len-1<m;i++){
int j=i+len-1;
if(len==1){
dp[i][j]=m*a[row][i];
}
else{
dp[i][j]=max(dp[i+1][j]+(m-len+1)*a[row][i],dp[i][j-1]+(m-len+1)*a[row][j]);
}
}
ans+=dp[0][m-1];
}
cout<<ans<<endl;
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(i+1, j) + (m-j+i) * a[row][i]`和`f(i, j-1) + (m-j+i) * a[row][j]`中的较大值。这是因为，我们可以选择取第i个元素或者第j个元素，所以我们需要比较这两种选择的得分，取较大的那个。
4. 对于每一行，`f(0, m-1)`就是这一行的最大得分。程序将所有行的最大得分累加起来，就得到了总的最大得分。
这个程序的时间复杂度是O(n*m^2)，因为它需要对每一行遍历所有可能的子数组。如果矩阵的大小非常大，那么这个程序可能会运行得比较慢。
注意，这个程序假设输入的矩阵的行数和列数不超过80，如果实际问题中矩阵的行数或列数可能超过这个值，那么需要相应地调整数组的大小。文章来源地址https://www.toymoban.com/news/detail-759837.html
代码实现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(i==j){
return dp[i][j]=a[row][i]*m;
}
else{
return dp[i][j]=max(f(i+1,j)+(m-j+i)*a[row][i],f(i,j-1)+(m-j+i)*a[row][j]);
}
}
int main() {
cin>>n>>m;
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>a[i][j];
}
for(row=0;row<n;row++){
memset(dp,0,sizeof(dp));
ans+=f(0,m-1);
}
cout<<ans<<endl;
return 0;
}
到了这里，关于[动态规划]矩阵取数游戏的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
