2000 NOIP 《方格取数》

#include<stdio.h>

#include<string.h>

#define MAX 10+2

int map[MAX][MAX];

int s[MAX*2][MAX][MAX];

int n;

void input(){

freopen("f.in","r",stdin);

freopen("f.out","w",stdout);

scanf("%d",&n);

memset(map,0,sizeof(map));

memset(s,-1,sizeof(s));

int a,b,x;

while(scanf("%d%d%d",&a,&b,&x)==3)

{if(a==0&&b==0&&x==0) break;

else map[b][a]=x;}

}

int max2(int a,int b)

{if(a>b) return a;

return b;}

int max4(int a,int b,int c,int d){

int x=max2(a,b),y=max2(c,d);

return max2(x,y); }

int sum(int k,int x1,int x2){

//if(s[k][x1][x2]!=-1) return s[k][x1][x2];

if(k==2) return s[k][x1][x2]=map[1][1]+map[1][2]+map[2][1];

int y1=k+1-x1,y2=k+1-x2,pp=map[x1][y1]+map[x2][y2];

if(x1==1&&y2==1)return s[k][x1][x2]=sum(k-1,x1,x2-1)+pp;

if(x1==1) return s[k][x1][x2]=max2(sum(k-1,x1,x2-1),sum(k-1,x1,x2))+pp;

if(y2==1) return s[k][x1][x2]=max2(sum(k-1,x1-1,x2-1),sum(k-1,x1,x2-1))+pp;

return s[k][x1][x2]=max4(sum(k-1,x1-1,x2-1),sum(k-1,x1-1,x2),sum(k-1,x1,x2-1),sum(k-1,x1,x2))+pp;

}

int main(){

input();

test1();test2(); //test

int ans=sum(2*n-2,n-1,n)+map[n][n];

printf("%d",ans);

return 0;

}