#include<bits/stdc++.h>
using namespace std;
int n,mp[10][10];
int f[10][10][10][10];
int dfs(int i1,int j1,int i2,int j2);
int main()
{
cin>>n;
int i,j,k;
cin>>i>>j>>k;
while(i!=0&&j!=0&&k!=0)
{
mp[i][j]=k;
cin>>i>>j>>k;
}
f[n][n][1][1]=mp[1][1]+mp[n][n];
cout<<dfs(1,1,1,1)<<endl;
return true;
}
int dfs(int i1,int j1,int i2,int j2)
{
if(i1<=0||i1>n||j1<=0||j1>n|| i2<=0||i2>n||j2<=0||j2>n) return 0;
int MAX=0;
if(f[i1][j1][i2][j2]!=0) return f[i1][j1][i2][j2];
MAX=max(MAX,dfs(i1+1,j1,i2+1,j2)+mp[i1][j1]+mp[i2][j2]);
MAX=max(MAX,dfs(i1,j1+1,i2,j2+1)+mp[i1][j1]+mp[i2][j2]);
MAX=max(MAX,dfs(i1+1,j1,i2,j2+1)+mp[i1][j1]+mp[i2][j2]);
MAX=max(MAX,dfs(i1,j1+1,i2+1,j2)+mp[i1][j1]+mp[i2][j2]);
if(i1==i2&&j1==j2) MAX-=mp[i1][j1];
return f[i1][j1][i2][j2]=MAX;
}
题解 P1004 【方格取数】
2018-07-16 00:00:00 题解
直接上代码，超级简洁哦。
