记录编号	125714	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.117 s
提交时间	2014-10-09 21:18:46	内存使用	4.25 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,a[101],f[101][101][101]={0},ans[101]={0};
void aDD(int [],int,int []);
void Add(int [],int);
void ADD(int []);
bool judge(int [],int []);
void out(int []);
void work()
{
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int d=1;d<=n;d++)//d为延伸长度;
	{
		for(int i=1;i<=n-d+1;i++)//i为起点;
		{
			int j=i+d-1;
			if(d==1)
			{
				f[i][j][0]=1;
				f[i][j][1]=2*a[i];
				continue;
			}
			int dx[101],lxx[101];
			aDD(f[i+1][j],a[i],dx);
			aDD(f[i][j-1],a[j],lxx);
			if(judge(dx,lxx)) memcpy(f[i][j],dx,sizeof(dx));
			else memcpy(f[i][j],lxx,sizeof(lxx));
			Add(f[i][j],2);
		}
	}
	ADD(f[1][n]);
}
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++) work();//求每行最优解再相加即可;
	out(ans);
	return 0;
}
void ADD(int a[])//每行最优解的相加;
{
	int m=10000;
	ans[0]=a[0];
	for(int i=1;i<=a[0];i++)
	{
		ans[i]+=a[i];
		if(ans[i]>=m)
		{
			ans[i+1]+=ans[i]/m;
			ans[i]%=m;
		}
	}
	if(ans[ans[0]+1]>0) ans[0]++;
}
void aDD(int a[],int b,int c[])
{
	int m=10000;
	for(int i=0;i<101;i++) c[i]=0;
	//memset(c,0,sizeof(c));c[]是dx数组传递过来的,无法赋值;
	c[0]=a[0];
	c[1]=b;	
	for(int i=1;i<=a[0];i++)
	{
		c[i]+=a[i];
		if(c[i]>=m)//高精加低精,万进制;
		{
			c[i+1]+=c[i]/m;
			c[i]%=m;
		}		
	}
	if(c[c[0]+1]>0) c[0]++;
}
bool judge(int a[],int b[])//比较a b数组的大小;
{	
	if(a[0]>b[0])return 1;
	if(a[0]<b[0])return 0;
	for(int i=a[0];i>0;i--)
	{	
		if(a[i]>b[i])return 1;
		else if(a[i]<b[i])return 0;
	}
	return 0;
}
void Add(int a[],int b)//高精乘;
{
	int m=10000,x=0;//x为进位;
	for(int i=1;i<=a[0];i++)
	{		
		a[i]=a[i]*b+x;
		x=a[i]/m;
		a[i]=a[i]%m;
	}
	if(x!=0)
	{
		a[0]++;
		a[a[0]]=x;	
	}
}
void out(int a[])//万进制数组输出;
{
	int len=a[0];
	cout<<a[len];
	for(int i=len-1;i>=1;i--)printf("%d%d%d%d",a[i]/1000,a[i]/100%10,a[i]%100/10,a[i]%10);
}