#include <bits/stdc++.h> using namespace std; /* 思路: 有来、回两次行走,而且不能有路径交叉。我们可以转换为一次行走,有两个人同时行走,形象地说为多线程。 只要每一时刻都保证两个人不在同一点上就可以保证路径不会交叉(这个仔细想想或者画一画就可以证明是对的)。 那么状态表示可以是f[i][j][k][l]表示第一个人在(i,j)第二个人在(k,l)时的最优解。 */ int N; int arr[100][100]; int f[15][15][15][15]; int main(){ int a,b,c; cin>>N; cin>>a>>b>>c; while(a!=0&&b!=0&&c!=0){ arr[a][b]=c; cin>>a>>b>>c; } for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ for(int k=1;k<=N;k++){ for(int l=1;l<=N;l++){ int tmp1=max(f[i][j-1][k][l-1],f[i-1][j][k][l-1]); int tmp2=max(f[i][j-1][k-1][l],f[i-1][j][k-1][l]); f[i][j][k][l]=max(tmp1,tmp2)+arr[i][j]; if(i!=k&&j!=l){ /*不在同一个点上*/ f[i][j][k][l]+=arr[k][l]; } } } } } cout<<f[N][N][N][N]; return 0; }
有话要说...