第一层做dfs爆搜，第二层做一次dp

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX(a,b) ((a)>=(b)?(a):(b))

int n;
int mp[15][15];
int dp[15][15];
int mx;

void input(){
	scanf("%d",&n);
	int x,y,w;
	while(scanf("%d%d%d",&x,&y,&w)!=EOF){
		mp[x][y]=w;
	}
}

void calc(int sum){
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=MAX(dp[i-1][j],dp[i][j-1])+mp[i][j];
		}
	}
	if(sum+dp[n][n]>mx){
		mx=sum+dp[n][n];
	}
}

void dfs(int x,int y,int sum){
	if(x==n&&y==n){
		calc(sum);
	}
	int tmp=mp[x][y];
	mp[x][y]=0;
	if(x+1<=n){
		dfs(x+1,y,sum+tmp);
	}
	if(y+1<=n){
		dfs(x,y+1,sum+tmp);
	}
	mp[x][y]=tmp;
}

void solve(){
	dfs(1,1,0);
	printf("%d",mx);
}

int main()
{
	input();
	solve();
	return 0;
}