NOIP2007矩阵取数游戏（dp + 高精）

分析

一开始可以想到的dp是用 $f\left[i\right]\left[j\right]$f[i][j]表示取到剩区间 $[i,j]$[i,j]时的最大得分，转移方程比较显然。
不过我采用了另一种做法，就是用 $f\left[i\right]\left[j\right]$f[i][j]表示取完了区间 $[i,j]$[i,j]的最大得分，相当于反过来做把。
这样可以得到转移方程:
$f\left[i\right]\left[j\right]=max\left(f\right[i+1\left]\right[j]+a[i],f[i\left]\right[j-1]+a[j\left]\right)\ast 2$f[i][j]=max(f[i+1][j]+a[i], f[i][j−1]+a[j])∗2
然后用高精度就可以了。

我为什么要挂这道题

万恶的memcpy函数，我以为是以下用法
memcpy(a, b, sizeof(a))
在WA了一万次之后，我怀疑起了人生，找到了以前A的代码，然后发现以前是人工复制的，在人工复制之后就A了！！百度了以下memcpy，原来根本不是我这么用（吐血了）。
这题做了我1个多小时！！！！！！！

下面贴代码

//f[i][j] = max(f[i+1][j] + a[i], f[i][j-1] + a[j]) * 2
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int mp[85][85], f[85][85][55], t1[55], t2[55], ans[55], tmp[55];
void add(int a[], int b[]){
	int i;
	for(i = 1; i <= 50; i++){
		a[i] += b[i];
		a[i+1] += a[i] / 10000;
		a[i] %= 10000;
	}
}
void com(int a[], int b[], int c[]){
	int i, j;
	for(i = 50; i >= 1; i--){
		if(b[i] > c[i]){
			for(j = 50; j >= 1; j--) a[j] = b[j]; 
			return;
		}
		if(b[i] < c[i]){
			for(j = 50; j >= 1; j--) a[j] = c[j];
			return;
		}
	}
	for(j = 50; j >= 1; j--) a[j] = b[j];
}
void mul(int a[], int c){
	int i;
	for(i = 1; i <= 50; i++) a[i] *= c;
	for(i = 1; i <= 50; i++){
		a[i+1] += a[i] / 10000;
		a[i] %= 10000;
	}
}
void print(int a[]){
	int i;
	for(i = 50; i >= 1; i--) if(a[i]) break;
	printf("%d", a[i]);
	for(i = i-1; i >= 1; i--) printf("%04d", a[i]);
}
int main(){
	int i, j, n, m, k;
	
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++){
		memset(f, 0, sizeof(f));
		for(j = 1; j <= m; j++){
			scanf("%d", &mp[i][j]);
			f[j][j][1] = mp[i][j] * 2;
		}
		for(j = m; j >= 1; j--){
			for(k = j+1; k <= m; k++){
				memset(t1, 0, sizeof(t1));
				memset(t2, 0, sizeof(t2));
				t1[1] = mp[i][j];
				t2[1] = mp[i][k];
				add(t1, f[j+1][k]);
				add(t2, f[j][k-1]);
				com(f[j][k], t1, t2);
				mul(f[j][k], 2);
				//printf("====%d %d ", j, k);
				//print(f[j][k]);
				//printf("\n");
			}
		}
		add(ans, f[1][m]);
		//print(ans);
		//printf("\n");
	}
	print(ans);
	return 0;
}