[NOIP2007 提高组] 矩阵取数游戏

这道题是卡了我蛮久的一道题，18年12月份的时候就在做，现在看当时的代码确实很多地方都不太一样。
但是，当时就拿了20分就放弃了，这次重新自己再写的时候，还是拿了20分……
这是巧合呢？还是这几年一点都没有长进呢

题目链接：矩阵取数游戏

题目大意：有n*m的矩阵，每次从行首或者是行尾取出一个数字，每次取n个数字，一共取m次。每次取数的价值为：被取走的数字 ∗ 2 i *2^{i} ∗2i (i是第i次取走这个数字)。求把全部数字取完的最大价值。

我的错因
我一开始的思路是贪心。想的贪心方法是，一行一行处理，把每一行直接按顺序从小到大取数，但是我没考虑到限制条件是只能从行首或者是行尾取数为不能实现严格的从小到大的关系。
比如：3 1 2 5 4
这串数字的最优解就是 3 1 2 4 5, 并不是我所想的1 2 3 4 5
所以，贪心的思路错误。

正解

1. 取得数字之间每行并不会产生影响，遵循最优子结构
2. 因为取走的数字都是行首或者是行尾的数字，会保持每一行之间剩下来的数字的区间的完整性，所以可以考虑区间DP

从每一行来单独考虑，假如说是第t行元素：
f [ i , j ] f[i, j] f[i,j]表示区间为 [ i , j ] [i,j] [i,j]时的最大价值，所以最终状态就是 f [ 1 , m ] f[1, m] f[1,m]
转移方程就是：
f [ i , j ] = m a x ( f [ i + 1 , j ] + a [ t , i ] ∗ 2 m − j + i , f [ i , j + 1 ] + a [ t , j ] ∗ 2 m − j + i ) f[i,j]=max(f[i+1,j]+a[t, i]*2^{m-j+i}, f[i, j+1]+a[t,j]*2^{m-j+i}) f[i,j]=max(f[i+1,j]+a[t,i]∗2m−j+i,f[i,j+1]+a[t,j]∗2m−j+i)
没在区间里面加入i或者是j之前，剩下的区间长度是：j-i
所以，此时取到的数字的次数为(m-j+i)

还要注意的一点就是， 2 80 = 1 , 208 , 925 , 819 , 614 , 629 , 174 , 706 , 176 2^{80}=1,208,925,819,614,629,174,706,176 280=1,208,925,819,614,629,174,706,176，已经超出了longlong的范围，需要使用到__int128

__int128是一个范围在 − 2 127 和 2 127 -2^{127}和2^{127} −2127和2127之间的整型变量，约为 1 0 38 10^{38} 1038左右

__int128 的输入和输出需要自己手写的代码

inline __int128 read()
{
	__int128 x=0, f=1; char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 

inline void output(__int128 x)
{
	if(x<0){putchar('-'); x=-x;}
	if(x>9)output(x/10);
	putchar(x%10+'0');
}

我在码代码的时候，还出现了一个小问题，就是如果是以下这个样子循环区间dp的话，就会造成更新过[1,3]之后，就无法再用[2,3]来更新[1,3]，所以，我的第一重循环改成了枚举长度。

for(int i=1;i<=m;++i)
	for(int j=i+1;j<=m;++j)

正解

#include
using namespace std;

const int nn=100;
__int128 b[nn], ans=0;//预处理出来2^m 
__int128 f[nn][nn], a[nn][nn];

inline __int128 read()
{
	__int128 x=0, f=1; char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 

inline void output(__int128 x)
{
	if(x<0)	{putchar('-'); x=-x;}
	if(x>9)	output(x/10);
	putchar	(x%10+'0');
}

int main()
{
	__int128 n, m;
	n=read(), m=read();
	b[0]=1, b[1]=2;
	for(int i=2;i<=m;++i)	b[i]=b[i-1]*2;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			a[i][j]=read();
	
	for(int t=1;t<=n;++t)
	{
		memset(f, 0, sizeof(f));
		for(int s=1;s<=m;++s)	f[s][s]=a[t][s]*b[m];
		
		for(int len=2;len<=m;++len)
			for(int i=1;i+len-1<=m;++i)
			{
				int k=m-len+1;
				f[i][i+len-1]=max(f[i+1][i+len-1]+a[t][i]*b[k], f[i][i+len-2]+a[t][i+len-1]*b[k]);
			}
		ans+=f[1][m];
	}
	output(ans);
	return 0;
}

还有一道题有点像是没有高精度的矩阵取数，而且是一维数组，如果觉得高精度对于自己有点难的话，可以考虑先做一下这道题：[USACO06FEB]Treats for the Cows G/S

自己思考一下，如果实在不会的话，可以看一下我的代码。

#include
using namespace std;

const int nn=2e3+100;

int n, a[nn];
int f[nn][nn];

inline int read()
{
	int x=0, f=1; char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}

int main()
{
	n=read();
	for(int i=1;i<=n;++i)	a[i]=read(), f[i][i]=a[i]*n;
	for(int len=2;len<=n;++len)
		for(int i=1;i+len-1<=n;++i)
		{
			int j=i+len-1;//区间终点 
			int k=n-j+i;//第几次取到这个数字
			f[i][j]=max(f[i+1][j]+a[i]*k, f[i][j-1]+a[j]*k); 
		}
	cout< 
附上小句子
  哪怕一百个愚笨的人在一起聚会，也无法产生一个智慧的人。