记录编号	269952	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.107 s
提交时间	2016-06-14 09:40:50	内存使用	1.10 MiB

#include<stdio.h>
#include<string.h>
/*================ struct ================*/
struct Bign{
	int big[20],len;
};
Bign ans={0},f[100][100]={0},num_2={0},a_c[100]={0};
/*================ variable ================*/
int n,m;
int a[200]={0};
/*================ function ================*/
/*================ bign_change ================*/
void bign_change(int d,Bign *c)
{
	while(d)
	{
		c->big[c->len++]=d%10000;
		d/=10000;
	}
}
/*================ bign_add ================*/
void bign_add(Bign *temp,Bign *c,Bign *d)
{
	int i;
	for(i=0;i<=temp->len;i++) temp->big[i]=0;
	if(c->len<d->len) temp->len=d->len;
	else temp->len=c->len;
	for(i=0;i<temp->len;i++)
	{
		temp->big[i]+=c->big[i]+d->big[i];
		if(temp->big[i]>=10000)
		  temp->big[i+1]+=temp->big[i]/10000,
		  temp->big[i]%=10000;
	}
	if(temp->big[temp->len]!=0) temp->len++;
}
/*================ bign_max ================*/
bool bign_max(Bign *c,Bign *d)
{
	if(c->len>d->len) return true;
	else if(c->len<d->len) return false;
	else
	{
		int i;
		for(i=c->len-1;i>=0;i--)
		  if(c->big[i]<d->big[i])
		    return false;
		  else if(c->big[i]>d->big[i])
		    return true;
	}
	return true;
}
/*================ bign_print ================*/
void bign_print(Bign *c)
{
	if(c->len==0)
	{
		printf("0\n");
		return;
	}
	int i;
	printf("%d",c->big[c->len-1]);
	for(i=c->len-2;i>=0;i--)
	  printf("%04d",c->big[i]);
	printf("\n");
}
/*================ bign_multiply ================*/
void bign_multiply(Bign *temp,Bign *c,Bign *d)
{
	int i,j;
	for(i=0;i<=temp->len;i++) temp->big[i]=0;
	temp->len=c->len+d->len-1;
	for(i=0;i<c->len;i++)
	  for(j=0;j<d->len;j++)
		temp->big[i+j]+=c->big[i]*d->big[j];
	for(i=0;i<temp->len;i++)
	if(temp->big[i]>=10000)
	{
		temp->big[i+1]+=temp->big[i]/10000;
		temp->big[i]%=10000;
	}
	if(temp->big[temp->len]!=0) temp->len++;
}
/*================  dp  ================*/
void dp()
{
	int i,j;
	memset(f,0,sizeof(f));
	for(j=1;j<=m;j++)
	{
		for(i=1;i<=m-j+1;i++)
		{
			Bign temp={0},a1={0},a2={0};
			bign_add(&a1,&f[i][j-1],&a_c[i+j-1]);
			bign_add(&a2,&f[i+1][j-1],&a_c[i]);
			bign_multiply(&temp,&a1,&num_2);
			bign_multiply(&f[i][j],&a2,&num_2);
			if(bign_max(&temp,&f[i][j]))
			  f[i][j]=temp;
		}
	}
	Bign Ans=ans;
	bign_add(&ans,&Ans,&f[1][m]);
}
/*================ quick read ================*/
inline int QR()
{
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	int x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x;
}
/*================ main ================*/
int _521()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	int i,j;
	n=QR(),m=QR();
	num_2.big[0]=2,num_2.len=1;
	for(i=1;i<=n;i++)
	{
		memset(a_c,0,sizeof(a_c));
		memset(a,0,sizeof(a));
		for(j=1;j<=m;j++)
		  a[j]=QR(),bign_change(a[j],&a_c[j]);
		dp();
	}
	bign_print(&ans);
	return 0;
}
int _520=_521();
int main(){;}