@[违规用户名9iL(8Z](/user/341801) 此题正解是 dp 。
by 初雪_matt @ 2021-07-19 09:12:09
@[初雪_matt](/user/360083) 我知道，但是看数据范围貌似记忆化也可做
by FChtholly @ 2021-07-19 09:13:02
@[违规用户名9iL(8Z](/user/341801) 详见[这篇题解](https://www.luogu.com.cn/blog/wozaixuexi/solution-p1004)
by 初雪_matt @ 2021-07-19 09:14:45
@[初雪_matt](/user/360083) 谢谢
by FChtholly @ 2021-07-19 09:18:20
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int a[107][107];
int dp[17][17][17][17];
int x,y,z;
int dfs(int x,int y,int x1,int y1){
if(dp[x][y][x1][y1]!=-1){
return dp[x][y][x1][y1];
}
if(x==n&&y==n&&x1==n&&y1==n){
return 0;
}
int ans=0;
if(x<n&&x1<n){
ans=max(ans,dfs(x+1,y,x1+1,y1)+a[x+1][y]+a[x1+1][y1]-a[x+1][y]*(x+1==x1+1&&y==y1));
}
if(x<n&&y1<n){
ans=max(ans,dfs(x+1,y,x1,y1+1)+a[x+1][y]+a[x1][y1+1]-a[x+1][y]*(x+1==x1&&y==y1+1));
}
if(y<n&&x1<n){
ans=max(ans,dfs(x,y+1,x1+1,y1)+a[x][y+1]+a[x1+1][y1]-a[x+1][y]*(x==x1+1&&y+1==y1));
}
if(y<n&&y1<n){
ans=max(ans,dfs(x,y+1,x1,y1+1)+a[x][y+1]+a[x1][y1+1]-a[x][y+1]*(x==x1&&y+1==y1+1));
}
dp[x][y][x1][y1]=ans;
return ans;
}
int main(){
cin>>n;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=n;k++){
for(int x=0;x<=n;x++){
dp[i][j][k][x]=-1;
}
}
}
}
do{
cin>>x>>y>>z;
a[x][y]=z;
}while(x!=0&&y!=0&&z!=0);
cout<<dfs(1,1,1,1)+a[1][1];
return 0;
}
```
by FChtholly @ 2021-07-19 10:17:22