记录编号	332780	评测结果	AAAAAWWWWA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	60
用户昵称	Hzoi_Go灬Fire	是否通过	未通过
代码语言	C++	运行时间	0.016 s
提交时间	2016-10-29 09:48:59	内存使用	0.38 MiB

/*
	Name: 矩阵取数游戏
	Copyright: 
	From：http://cogs.pro/cogs/problem/problem.php?pid=96
	Author: Go灬Fire 
	Date: 19/10/16 07:31
	Description: f[i][j]代表已经取完区间i~j获得的最大分数 
*/
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define Inf 0x7f7f7f7f
#define LL long long
using namespace std;
const int maxn=110;
int n;
double a[maxn],f[maxn][maxn],ans;
void Init();
 
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	int T; 
	scanf("%d%d",&T,&n);
	for(int i=1;i<=T;i++)Init();
	printf("%.0lf",ans);
    getchar();getchar();
    return 0;
}
void Init(){
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
	for(int d=1;d<=n;d++){
		for(int i=1;i<=n-d+1;i++){
			int j=i+d-1;
			double b=f[i+1][j]+a[i],c=f[i][j-1]+a[j];
			if(b>c)f[i][j]+=2*b;
			else f[i][j]+=2*c;
		}
	}
	ans+=f[1][n];
}