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

一道考试中的题，来写篇题解。

我们首先发现每行是独立的，于是可以一行一行的处理。

又发现贪心有后效性，遂准备 dp。

对于每行，设

dp_{l,r}

为除了区间

[l,r]

，其它数都取完的最大得分。

所以这一行的最大得分为

\max_{1\le x\le m}dp_{x,x-1}

。

转移也很好想了，设

s=r-l+1

，

a

数组为该行的数字。

dp_{l,r}=\max(dp_{l-1,r}+a_{l-1}\times 2^{n-s},dp_{l,r+1}+a_{r+1}\times 2^{n-s})

此式转移一个是取左边一个是取右边，所以显然成立。

最后就是注意

dp

的转移顺序了，还有要开 __int128。

一道水绿就这样的切了。

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[110];
__int128 dp[110][110];
__int128 sum=0;
void write(__int128 x){
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cin>>a[j];
		dp[1][m]=0;
		for(int j=1;j<=m;j++)
			for(int k=m;k>=j-1;k--)
				dp[j][k]=max(dp[j-1][k]+a[j-1]*(__int128(1)<<(j-1+m-k)),dp[j][k+1]+a[k+1]*(__int128(1)<<(j-1+m-k)));
		__int128 ans=0;
		for(int j=1;j<=m;j++) ans=max(ans,dp[j][j-1]);
		sum+=ans;
	}
	write(sum);
	return 0;
}

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

文章操作

相关推荐

评论

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