记录编号	151105	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] 蚂蚁寻路	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	1.256 s
提交时间	2015-03-03 18:42:46	内存使用	127.29 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int L_N=100+10;
const int L_K=20+5;
const int INF=1e9;
int f[L_N][L_N][L_N][L_K],s[L_N][L_N],N,M,K;
int S(int j,int i1,int i2){
	//printf("j:%d i1:%d i2:%d ret:%d\n",j,i1,i2,s[j][i2]-s[j][i1-1]);
	return s[j][i2]-s[j][i1-1];
}
void set_max(int & a,int b){
	a=max(a,b);
}
int main(){
	//freopen("in.txt","r",stdin);
	freopen("zjoi13_ant.in","r",stdin);
	freopen("zjoi13_ant.out","w",stdout);
	scanf("%d %d %d",&N,&M,&K);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){
		int t; scanf("%d",&t);
		s[j][i]=t+s[j][i-1];
	}
	
	
	for(int i=0;i<=N;i++) for(int j=0;j<=M;j++){
		for(int h=0;h<=N;h++) for(int k=0;k<=2*K+1;k++){
			f[i][j][h][k]=-INF;
		}
	}
	
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){
		for(int h=1;h<=i;h++) f[i][j][h][1]=S(j,h,i);
	}
	
	for(int k=1;k<=2*K+1;k++){
		for(int j=1;j<=M;j++){
			for(int i=1;i<=N;i++){
				if(k%2){
					int mx=-INF;
					for(int h=i;h>=1;h--){
						int ad=S(j,h,i);
						set_max(f[i][j][h][k],f[i][j-1][h][k]+ad);
						set_max(f[i][j][h][k],mx+ad);
						set_max(mx,f[i][j-1][h][k-1]);
					}
				}else {
					int mx=-INF;
					for(int h=1;h<=i;h++){
						int ad=S(j,h,i);
						set_max(f[i][j][h][k],f[i][j-1][h][k]+ad);
						set_max(f[i][j][h][k],mx+ad);
						set_max(mx,f[i][j-1][h][k-1]);
					}
				}
			}
		}
	}
	
	int ans=-INF;
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){
		for(int h=1;h<=i;h++){
			/*if(f[i][j][h][2*K+1]>ans){
				printf("f[%d][%d][%d][%d]=%d\n",i,j,h,2*K+1,f[i][j][h][2*K+1]);
			}*/
			set_max(ans,f[i][j][h][2*K+1]);
		}
	}
	
	printf("%d\n",ans);
	return 0;
}