是我想简单了...
by zlinda @ 2022-10-01 21:28:50
换了一个点错,还是80......
```cpp
#include<bits/stdc++.h>
using namespace std;
int dp[15][15][15][15],a[15][15];
int main()
{
int n,i,j,l,x,y,z;
cin>>n;
do{
cin>>x>>y>>z;
a[x][y]=z;
}while(x!=0&&y!=0&&z!=0);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(l=2;l<=2*n;l++)
{
if(l>i+n||l>j+n) break;
x=max(dp[i-1][l-i][j-1][l-j],dp[i-1][l-i][j][l-j-1]);
y=max(dp[i][l-i-1][j-1][l-j],dp[i][l-i-1][j][l-j-1]);
dp[i][l-i][j][l-j]=max(x,y);
if(i!=j) dp[i][l-i][j][l-j]+=a[i][l-i]+a[j][l-j];
else dp[i][l-i][j][l-j]+=a[i][l-i];
}
cout<<dp[n][n][n][n];
return 0;
}
```
by zlinda @ 2022-10-01 21:45:43
终于过了...前面忘了判断l>i&&l>j,数据又比较水,数组一直没越界查了半天才发现...
```cpp
#include<bits/stdc++.h>
using namespace std;
long long dp[15][15][15][15],a[15][15];
int main()
{
int n,i,j,l,x,y,z;
cin>>n;
do{
cin>>x>>y>>z;
a[x][y]=z;
}while(x!=0&&y!=0&&z!=0);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(l=2;l<=2*n;l++)
{
if(l>i&&l>j)
{
if(l>i+n||l>j+n) break;
x=max(dp[i-1][l-i][j-1][l-j],dp[i-1][l-i][j][l-j-1]);
y=max(dp[i][l-i-1][j-1][l-j],dp[i][l-i-1][j][l-j-1]);
dp[i][l-i][j][l-j]=max(x,y);
if(i!=j) dp[i][l-i][j][l-j]+=a[i][l-i]+a[j][l-j];
else dp[i][l-i][j][l-j]+=a[i][l-i];
}
}
cout<<dp[n][n][n][n]<<"\n";
return 0;
}
```
by zlinda @ 2022-10-01 22:11:36
@[zlinda](/user/698678) 这个思路不对吗,难道?我也是第三组卡不过去
by azhe_DaShu @ 2022-10-03 15:28:31
@[azhe21521](/user/693079) 清零的思路难道不对吗
by azhe_DaShu @ 2022-10-03 15:30:25
@[azhe21521](/user/693079) 您可以看看我后面的自问自答,两次局部dp并不能保证全局最优,还是要同时考虑两条路线,这是我加了注释的版本
```cpp
#include<bits/stdc++.h>
using namespace std;
long long dp[15][15][15][15],a[15][15];
int main()
{
int n,i,j,l,x,y,z;
cin>>n;
do{
cin>>x>>y>>z;
a[x][y]=z;
}while(x!=0&&y!=0&&z!=0);
for(i=1;i<=n;i++)//第一次路径当前横坐标
for(j=1;j<=n;j++)//第二次路径当前横坐标
for(l=2;l<=2*n;l++)//当前总步数
{
if(l>i&&l>j)//注意判断小心越界
{
if(l>i+n||l>j+n) break;
x=max(dp[i-1][l-i][j-1][l-j],dp[i-1][l-i][j][l-j-1]);
y=max(dp[i][l-i-1][j-1][l-j],dp[i][l-i-1][j][l-j-1]);
dp[i][l-i][j][l-j]=max(x,y);
if(i!=j) dp[i][l-i][j][l-j]+=a[i][l-i]+a[j][l-j];
else dp[i][l-i][j][l-j]+=a[i][l-i];//当两点重合时只加一次
}
}
cout<<dp[n][n][n][n]<<"\n";
return 0;
}
```
希望能有帮助
by zlinda @ 2022-10-03 15:44:28
哈哈哈,找到有缘人了
by 瞬间爆炸! @ 2022-10-18 14:50:19