题目传送门

我就是人见人爱，花见花开的"Carlos_01dao09"，下面来讲一下矩阵取数游戏这道题的题解（发不了题解）。

复述题目

现在输入一个n*m的矩阵，游戏规则如下

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

现在要你求出取数后的最大得分。

输入输出样例

输入 #1

2 3
1 2 3
3 4 2

输出 #1

82

说明/提示

数据范围

对于 60% 的数据，满足 1≤n,m≤30，答案不超过 10^16。
对于 100% 的数据，满足 1≤n,m≤80，0≤ai,j​≤1000。

讲解思路

这题我们用的是动态规划，区间DP,不过这也不能满分，我们看一下数据范围，对于 100% 的数据，满足 1≤n,m≤80，0≤ai,j​≤1000，2^80次方不能用long long来表示，所以我们要用高精度+区间DP，这难度一般是CSP-J的压轴题了(只是我这么认为，有可能是我见识太短浅了)，废话不多说，我们直接开始讲解：

怎么做

我们不要直接就联系起来，不然可能会很乱，如果是现场考试，我会先把这60分拿到手再去想怎么做100分的，所以我们我们先看不用高精度怎么做。

区间dp(不考虑高精度)

先输入n，m，然后我们先用long long做一遍，输入a[j]，注意，不是二维数组，而是j，但我们还是要双层循环，然后我们在i那层循环里面一边输入一边处理，先初始化二维dp数组，dp[0][m+1]赋值为0，还要定义一个变量ans(记得用long long) ，它就是用来记录每次取的数的和，我们在主函数那层再新建一个变量z，就是输出的最大得分，然后我们在搞一个for循环，l从m+1到2，l--，再搞一个for循环，k从0开始，到m-l(这里本来是m+1-l-1，简化了)，然后我们在k这层for循环里定义一个j，每次赋值为k+l-1，现在我们要分情况来看dp[k][j]。

三种情况

• k等于0

dp[k][j]=dp[k][j+1]+a[j]*pow(2,m-j+k+1);

这里我就不过多解释了。

因为但凡学过区间dp的都看得懂 。

• j等于m+1

dp[k][j]=dp[k-1][j]+a[k]*pow(2,m-j+k+1);

• k不等于0与j不等于m+1

 这里其实就是不满足上面两个条件，所以用else if也行。

dp[k][j]=max(dp[k-1][j]+a[k]*pow(2,m-j+k+1),dp[k][j+1]+a[j]*pow(2,m-j+k+1));

有点长…… 

最大dp

如果l等于2就取最大值。

得分相加

在for循环i的那层里面相加。

上60分代码

#include<bits/stdc++.h>
using namespace std;
long long a[81],dp[81][81];

int main() {
	int n,m;
	cin>>n>>m;
	long long z=0,ans;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[j];
		}
		dp[0][m+1]=0;
		ans=0;
		for(int l=m+1;l>=2;l--)
		{
			for(int k=0;k<=m+1-l+1;k++)
			{
				int j=k+l-1;
				if(k==0) 
				{
					dp[k][j]=dp[k][j+1]+a[j]*pow(2,m-j+k+1);
				}
				if(j==m+1)
				{
					dp[k][j]=dp[k-1][j]+a[k]*pow(2,m-j+k+1);
				}
				if(k!=0&&j!=m+1)
				{
					dp[k][j]=max(dp[k-1][j]+a[k]*pow(2,m-j+k+1),dp[k][j+1]+a[j]*pow(2,m-j+k+1));
				}
				if(l==2) 
				{
					ans=max(ans,dp[k][j]);
				}
			}
		}
		z+=ans; 
	} 
	cout<<z;

	return 0;
}

考虑高精度

这里其实挺简单的，就是考你高精度加法、高精度乘低精度和比较大整数。

不过注意a数组还是用long long，dp数组，ans，z就要用字符串。

接下来把加，乘，比较各个高精度算法简单讲一下(详情见这里)

比较大整数

其实就先看数位多少，也就是字符串长度，哪个长哪个就个大，如果一样，那就直接比a和b。

高精度加法

就是把它储存到数组里，然后处理进位，最后看最高位要不要加一，然后用一个s字符串把每个数字连接起来，返回就行。

高精度乘低精度

把每一位字符和数字相乘，再和加法一样处理进位并用字符串s把数字连接。

需要更改的地方

我把需要更改的地方写出来：

这里是需要添加在开头的：

for(int o=1;o<=m;o++)s[o]=chen(s[o-1],2);

下面是需要更改的：

dp[k][j]=jia(dp[k][j+1],chen(s[m-j+k+1],a[j]));

dp[k][j]=jia(dp[k-1][j],chen(s[m-j+k+1],a[k]));

dp[k][j]=bijiao(jia(dp[k-1][j],chen(s[m-j+k+1],a[k])),jia(dp[k][j+1],chen(s[m-j+k+1],a[j])));

ans=bijiao(ans,dp[k][j]);

z=jia(z,ans);

这里是要添加在最后的：

for(int i=z.length()-1;i>=0;i--)cout<<z[i];

上代码

以下是这道题的代码

#include <bits/stdc++.h>
using namespace std;
string bijiao(string a,string b){
	if(a.length()>b.length())return a;
	else if(a.length()<b.length())return b;
	for(int i=a.length()-1;i>=0;i--)
		if(a[i]>b[i])return a;
	else if(a[i]<b[i])return b;
	
	return a;
}

string chen(string a,int b){
	int la=a.length(),lc;
	lc=la;
	int aa[la],cc[la+100];
	cc[lc]=0;
	for(int i=0;i<la;i++){
		aa[i]=a[i]-'0';	
		cc[i]=aa[i]*b;		
	}
	for(int i=0;i<lc;i++){
		cc[i+1]+=cc[i]/10;
		cc[i]%=10;
	}
	while(cc[lc]>0){
		cc[lc+1]=cc[lc]/10;
		cc[lc]%=10;
		lc++;
	}
	string s="";
	for(int i=0;i<lc;i++)
	{
		s=s+char(cc[i]+'0');
	}
	return s;
}
string jia(string a,string b){
	int la=a.length(),lb=b.length(),lc;
	lc=0;
	int aa[la],bb[lb],cc[max(la,lb)+1],jw=0;
	for(int i=0;i<la;i++)aa[i]=a[i]-'0';
	for(int i=0;i<lb;i++)bb[i]=b[i]-'0';
	for(int i=0;i<min(la,lb);i++){
		cc[i]=aa[i]+bb[i]+jw;
		jw=cc[i]/10;
		cc[i]=cc[i]%10;
		lc++;}
	while(lc<la){	
		cc[lc]=aa[lc]+jw;
		jw=cc[lc]/10;
		cc[lc]%=10;
		lc++;}
	while(lc<lb){
		cc[lc]=bb[lc]+jw;
		jw=cc[lc]/10;
		cc[lc]%=10;
		lc++;}
	while(jw>0){
		cc[lc]=jw;
		lc++;jw=0;
	}
	string s="";
	for(int i=0;i<lc;i++)
	{
		s=s+char(cc[i]+'0');
	}
	return s;
}
int main() {
	int n,m;
	cin>>n>>m;
	string z="0",ans;
	long long a[m+1];
	string dp[m+2][m+2];
	string s[m+1];
	s[0]="1";
	for(int o=1;o<=m;o++)s[o]=chen(s[o-1],2);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cin>>a[j];
		dp[0][m+1]="0";
		ans="0";
		for(int l=m+1;l>=2;l--){
			for(int k=0;k<=m+1-l+1;k++)
			{
				int j=k+l-1;
				if(k==0)dp[k][j]=jia(dp[k][j+1],chen(s[m-j+k+1],a[j]));
				if(j==m+1)dp[k][j]=jia(dp[k-1][j],chen(s[m-j+k+1],a[k]));
				if(k!=0&&j!=m+1)
					dp[k][j]=bijiao(jia(dp[k-1][j],chen(s[m-j+k+1],a[k])),
						jia(dp[k][j+1],chen(s[m-j+k+1],a[j])));
				if(l==2)
					ans=bijiao(ans,dp[k][j]);
			}
		}
		z=jia(z,ans);
	}
	for(int i=z.length()-1;i>=0;i--)cout<<z[i];
	return 0;
}

最后

以上就是这道题的题解，希望关注点个赞。