谁说不能用双重dp的方法？？？@[Daidly](/user/271736) 能不能不要把自己做不到的归结为大家都做不到。。。
```cpp
# include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50 + 5;
int max(int a,int b){
return a > b ? a : b;
}
int a[MAX_N][MAX_N];
int sum[MAX_N][MAX_N][MAX_N][MAX_N];
int n,x,y,z;
int main(){
cin>>n>>x>>y>>z;
while(x && y && z){
a[x][y] = z;
cin>>x>>y>>z;
}
for (int i = 1 ; i <= n ; i ++){
for (int j = 1 ; j <= n ; j ++){
for (int h = 1 ; h <= n ; h ++){
for (int k = 1 ; k <= n ; k ++){
int tmp1 = max(sum[i - 1][j][h - 1][k] , sum[i][j - 1][h][k - 1]);
int tmp2 = max(sum[i - 1][j][h][k - 1] , sum[i][j - 1][h - 1][k]);
sum[i][j][h][k] = max(tmp1 , tmp2) + a[i][j];
if (i != h && j != k){
sum[i][j][h][k] += a[h][k];
}
}
}
}
}
cout<<sum[n][n][n][n];
}
```
by ker_xyxyxyx_xxs @ 2021-07-22 09:01:57
本题需要使用双线动规，即两条路同时走。
因为只能向下和向右，所以（i，j）这个点一定是第i+j-2步走到的
因此只需枚举k，i1，i2即可
注意同一个点只取一次。
by zry20100305 @ 2021-07-22 09:02:58
@[ker_xyxyxyx_xxs](/user/335477) 我的意思是 $O(n^2)$ 的两次 dp，可能描述有些不清，对不起。
by Daidly @ 2021-07-22 09:04:35
哦哦哦，对不起
不该喷人的（最近有些暴躁
by ker_xyxyxyx_xxs @ 2021-07-22 09:05:48
@[Daidly](/user/271736)
by ker_xyxyxyx_xxs @ 2021-07-22 09:06:09
@[Daidly](/user/271736)
本题需要使用双线动规，即两条路同时走。
因为只能向下和向右，所以（i，j）这个点一定是第i+j-2步走到的
因此只需枚举k，i1，i2即可
注意同一个点只取一次。
by zry20100305 @ 2021-07-22 09:12:26
@[zry20100305](/user/453132) 这和我hack的题解思路不一样啊，你说的没问题啊
by Daidly @ 2021-07-22 09:14:55
```cpp
#include<bits/stdc++.h>
#define reint register int
#define forr(i,a,b) for(reint i=(a);i<=(b);i++)
using namespace std;
const int N=15;
int a[N][N];
int f[N][N][N][N];
int n;
int x,y,z;
inline int max(int i,int j,int qwq,int qaq)
{
return max(max(f[i-1][j][qwq][qaq-1],f[i-1][j][qwq-1][qaq]),max(f[i][j-1][qwq-1][qaq],f[i][j-1][qwq][qaq-1]));
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
cin>>x>>y>>z;
while(x&&y&&z)
{
a[x][y]=z;
cin>>x>>y>>z;
}
// forr(i,1,n)
// {
// forr(j,1,n)
// {
// cout<<a[i][j]<<' ';
// }
// cout<<endl;
// }
// cout<<endl;
forr(i,1,n)
{
forr(j,1,n)
{
forr(qwq,1,n)
{
forr(qaq,1,n)
{
f[i][j][qwq][qaq]=max(i,j,qwq,qaq)+a[i][j];
if(i!=qwq || j!=qaq)
{
f[i][j][qwq][qaq]+=a[qwq][qaq];
}
}
}
}
}
cout<<f[n][n][n][n];
return 0;
}
```
by Link_Cut_Y @ 2021-08-13 10:42:44