@[段落](/user/392327)
给你卡过了
```
#include<bits/stdc++.h>
using namespace std;
int n,a[15][15],x,y,b,ans = -2e9,c[15][15], cnt;
void dfs(int x,int y,int k,int sum)
{//当前正在准备处理(x,y),是第k次，之前已经获取的和为sum
cnt++;
if(cnt>100000000)return;
if(x==n&&y==n&&k==1)
{
int t=a[x][y];
a[x][y]=0;
dfs(1,1,2,sum+t);
a[x][y]=t;
return;
}
if(x==n&&y==n&&k==2){ans=max(ans,sum); return;}
if(x+1<=n)
{
int t=a[x][y];
a[x][y]=0;
dfs(x+1,y,k,sum+t);
a[x][y]=t;
}
if(y+1<=n)
{
int t=a[x][y];
a[x][y]=0;
dfs(x,y+1,k,sum+t);
a[x][y]=t;
}
return;
}
int main(){
cin>>n;
while(1)
{
cin>>x>>y>>b;
if(x==0&&y==0&&b==0)break;
a[x][y]=b;
}
dfs(0,0,1,0);
cout<<ans;
return 0;
}
```
by __zhy__ @ 2023-10-15 11:23:13
记忆化一般来说过不了，但如果您只是要过的话，楼上代码参考。
DP正解:
```cpp
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
int dp[15][15][15][15];
int a[15][15];
int main()
{
int n;
cin>>n;
while(1)
{
int x,y,z;
cin>>x>>y>>z;
if(x+y+z==0)break;
a[x][y]=z;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int l=1;l<=n;l++)
for(int k=1;k<=n;k++)
{
dp[i][j][l][k]=max(max(dp[i-1][j][l-1][k],dp[i-1][j][l][k-1]),max(dp[i][j-1][l-1][k],dp[i][j-1][l][k-1]))+a[i][j]+a[l][k];
if(l==i&&j==k)
dp[i][j][l][k]-=a[i][j];
}
cout<<dp[n][n][n][n];
return 0;
}
```
by fedoralxy @ 2023-10-16 15:01:44
记忆化还是可以过的，不过不能分两次搜。
放在一起搜就可以了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, f[11][11][11][11], s[101][101];
int dfs(int x, int y, int x2, int y2)
{
if(f[x][y][x2][y2] != -1) return f[x][y][x2][y2];
if(x == n && y == n && x2 == n && y2 == n) return 0;
int maxn = -1;
if(x < n && x2 < n)
{
if(x + 1 == x2 + 1 && y == y2) maxn = max(maxn, dfs(x + 1, y, x2 + 1, y2) + s[x + 1][y]);
else maxn = max(maxn, dfs(x + 1, y, x2 + 1, y2) + s[x + 1][y] + s[x2 + 1][y2]);
}
if(x < n && y2 < n)
{
if(x + 1 == x2 && y == y2 + 1) maxn = max(maxn, dfs(x + 1, y, x2, y2 + 1) + s[x + 1][y]);
else maxn = max(maxn, dfs(x + 1, y, x2, y2 + 1) + s[x + 1][y] + s[x2][y2 + 1]);
}
if(y < n && y2 < n)
{
if(y + 1 == y2 + 1 && x == x2) maxn = max(maxn, dfs(x, y + 1, x2, y2 + 1) + s[x][y + 1]);
else maxn = max(maxn, dfs(x, y + 1, x2, y2 + 1) + s[x][y + 1] + s[x2][y2 + 1]);
}
if(x2 < n && y < n)
{
if(x2 + 1 == x && y2 == y + 1) maxn = max(maxn, dfs(x, y + 1, x2 + 1, y2) + s[x][y + 1]);
else maxn = max(maxn, dfs(x, y + 1, x2 + 1, y2) + s[x][y + 1] + s[x2 + 1][y2]);
}
return f[x][y][x2][y2] = maxn;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) for(int o = 1; o <= n; o ++) for(int p = 1; p <= n; p ++) f[i][j][p][o] = -1;
while(1)
{
int a, b, c; cin >> a >> b >> c;
s[a][b] = c;
if(a == 0 && b == 0 && c == 0) break;
}
cout <<dfs(1, 1, 1, 1) + s[1][1] << '\n';
return 0;
}
```
洛谷复制缩进日常爆炸，将就着看吧·-·
by ST_AS_IS_ZHY @ 2024-02-03 10:29:58