记录编号	329461	评测结果	AAWAAA
题目名称	[NOIP 2000]方格取数	最终得分	83
用户昵称	ciyou	是否通过	未通过
代码语言	C++	运行时间	0.020 s
提交时间	2016-10-25 15:58:55	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[20][20],l,f[20][20],ans=0;

int pick(int x,int y);

int dfs(int x,int y,int now,int e){
    if(f[x][y]==e) map[x][y]=0;
    if(x<=0||x>l||y<=0||y>l){
        return 0;
    }
    if(x==l&&y==l){
        if(now>f[x][y]){
            f[x][y]=now;
            return now;
        }
    }
    int a=dfs(x+1,y,now+map[x][y],e);
    int b=dfs(x,y+1,now+map[x][y],e);
    if(a+b>0){
        f[x][y]=max(a,b);
        return f[x][y];
    }
    return 0;
}

void insert(int x,int y,int w){
    map[x][y]=map[2*l-x][2*l-y]=w;
    return;
}

int pick(int x,int y){
    int ret=map[x][y];
    map[x][y]=0;
    if(x<=l&&y<=l) map[2*l-x][2*l-y]=0;
    return ret;
}

int main(){
    freopen("fgqs.in","r",stdin);
    freopen("fgqs.out","w",stdout);
    scanf("%d",&l);
    memset(map,0,sizeof(map));
    memset(f,0,sizeof(f));
    int a,b;
    while(scanf("%d%d",&a,&b)&&a!=0&&b!=0){
        int temp;
        scanf("%d",&temp);
        insert(a,b,temp);
    }
    int e;
    int k=map[l][l];
    e=dfs(1,1,0,-1);
    f[l][l]=0;
    ans=e+dfs(1,1,0,e)+k;
    cout<<ans;
    fclose(stdin);
    fclose(stdout);
    return 0;
}