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

我们可以发现，这个矩阵的每行都是独立的，于是我们可以分别计算每一行的最大得分。

考虑区间 DP。

对于每一行，我们设

f_{l,r}

表示将

[l,r]

取完后，所获得的最大得分。

因为每次只能取行首或行尾，所以我们可以推出状态转移方程：

f_{l,r} = \max (f_{l,r-1} + 2^{n - len + 1} \times a_r , f_{l+1,r} + 2^{n-len+1} \times a_l)

总时间复杂度：

O(nm^2)

。

要注意本题需要开__int128。

代码：

CPP

#include<cstdio>
#define max(a,b) (a>b?a:b)
using namespace std;
const int N=90,mod=2,mod10=10;
__int128 f[N][N],v[N],ans;
__int128 power(__int128 a,__int128 b){
	__int128 ans=1;
	while(b){
		if(b%mod) ans=ans*a;
		b/=mod;
		a=a*a;
	}
	return ans;
}
__int128 read(){
	__int128 x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+(c^48);
		c=getchar();
	}
	return x*f;
}
void write(__int128 x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
int main(){
	int m,n;//这里的 n 和 m 与原题相反
	scanf("%d%d",&m,&n);
	while(m--){
		for(int i=1;i<=n;i++){
			v[i]=read();
			f[i][i]=power(2,n)*v[i];
		}
		for(int len=2;len<=n;len++){
			for(int i=1;i+len-1<=n;i++){
				int j=i+len-1;
				f[i][j]=max(f[i][j-1]+power(2,n-len+1)*v[j],f[i+1][j]+power(2,n-len+1)*v[i]);
			}
		}
		ans+=f[1][n];
	}
	write(ans);
	return 0;
}

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

文章操作

相关推荐

评论

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