---

 

动态规划Yes？

设i为路径长度，（为什么i这一维可以省掉见下）f[j][k]表示第一个点到了(j,i-j),第二个点到了(k,j-k)

则

int ji=i-j,ki=i-k;        f[j][k]=max(f[j][k],f[j-1][k-1]);        f[j][k]=max(f[j][k],f[j-1][k]);        f[j][k]=max(f[j][k],f[j][k-1]);        f[j][k]+=s[j][ji];        if(j!=k&&ji!=ki) f[j][k]+=s[k][ki];

由于只从上一个状态转移，所以可以像01背包那样倒序循环，保证只访问上一个状态。

#include
     
      #include
      
       #include
       
        #define R register intusing namespace std;int n,cnt,f[10][10],s[10][10];struct node {    int u,v,w;}a[82];inline int g() {    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;    do ret=(ret<<3)+(ret<<1)+(ch^48); while(isdigit(ch=getchar())); return ret*fix;}inline int max(int a,int b) {
   return a>b?a:b;}signed main() {    n=g(); R u=g(),v=g(),w=g();    while(u&&v&&w) {a[++cnt].u=u,a[cnt].v=v,a[cnt].w=w;u=g(),v=g(),w=g();}    for(R i=1;i<=cnt;i++) {s[a[i].u][a[i].v]=a[i].w;}    for(R i=1;i<=(n<<1);i++) for(R j=i;j>=1;j--) for(R k=i;k>=1;k--) {        R ji=i-j,ki=i-k;        f[j][k]=max(f[j][k],f[j-1][k-1]);        f[j][k]=max(f[j][k],f[j-1][k]);        f[j][k]=max(f[j][k],f[j][k-1]);        f[j][k]+=(s[j][ji]+s[k][ki]*(j!=k));    } printf("%d\n",f[n][n]);}
       
      
     

2019.3.1