记录编号	100691	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] 蚂蚁寻路	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.706 s
提交时间	2014-05-07 12:51:52	内存使用	4.81 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZEN=110,INF=0x7fffffff/2;
int N,M;
int K;
int board[SIZEN][SIZEN]={0};
int rowsum[SIZEN][SIZEN]={0};//某个数向下到选定的行的和
void print(int s[SIZEN][SIZEN]){
	for(int i=0;i<=N+1;i++){
		for(int j=0;j<=M+1;j++){
			if(s[i][j]==-INF) cout<<"#"<<" ";
			else cout<<s[i][j]<<" ";
		}
		cout<<endl;
	}
}
void getrowsum(int k){//选定第k行为底部
	memset(rowsum,0,sizeof(rowsum));
	for(int j=1;j<=M;j++){
		rowsum[k][j]=board[k][j];
		for(int i=k-1;i>=1;i--) rowsum[i][j]=rowsum[i+1][j]+board[i][j];
	}
}
int f[2][SIZEN][SIZEN]={0};
int g[2][SIZEN][SIZEN]={0};
void setneg(int s[SIZEN][SIZEN]){
	for(int i=0;i<SIZEN;i++){
		for(int j=0;j<SIZEN;j++) s[i][j]=-INF;
	}
}
int testbot(int b){
	getrowsum(b);
	memset(f[0],0,sizeof(f[0]));
	memset(g[0],0,sizeof(g[0]));
	int ans=-INF;
	for(int t=1;t<=2*K+1;t++){
		setneg(f[t&1]);setneg(g[t&1]);
		if(t&1){//这是一个"突起",应当比前面的高
			for(int j=t;j<=M;j++){//不可能在第t列左边
				for(int i=1;i<=b;i++){
					f[1][i][j]=max(f[1][i][j-1],g[0][i+1][j-1])+rowsum[i][j];
					g[1][i][j]=max(g[1][i-1][j],f[1][i][j]);
				}
			}
		}
		else{//这是一个"凹陷",应当比前面的低
			for(int j=t;j<=M;j++){
				for(int i=b;i>=1;i--){
					f[0][i][j]=max(f[0][i][j-1],g[1][i-1][j-1])+rowsum[i][j];
					g[0][i][j]=max(g[0][i+1][j],f[0][i][j]);
				}
			}
		}
		//cout<<t<<endl;print(f[t&1]);cout<<endl;print(g[t&1]);cout<<endl<<endl;
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++) ans=max(ans,f[1][i][j]);
	}
	return ans;
}
void work(void){
	int ans=-INF;
	if(K==0) ans=max(ans,testbot(1));
	for(int i=2;i<=N;i++) ans=max(ans,testbot(i));
	printf("%d\n",ans);
}
void read(void){
	scanf("%d%d%d",&N,&M,&K);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++) scanf("%d",&board[i][j]);
	}
}
int main(){
	freopen("zjoi13_ant.in","r",stdin);
	freopen("zjoi13_ant.out","w",stdout);
	read();
	work();
	return 0;
}