UVA 1347 Tour（双调欧几里得旅行商）

思路：走一圈可以转化为两个人同时从起点出发，沿两条不同路走到终点。但如果用f(i)(j)表示第一个人走到i，第二个人走到j，还需走的距离，则由状态（i，j）转移时发现状态转移困难（例如，能否从i转移到j，状态中无法体现，也即无法保证两人是否走到过同一点）。所以，转换状态表示：f(i)(j)表示1---max(i,j)全部走过，两人分别在i、j时，还需走的距离。又因为f(i)(j)=f(j)(i)，所以，设i>j。但此时又因为如果从i转移到i+1，i+2，i+3，........可能出现某些点并未走过的情况。所以，强制每次转移时，两人中只能有一人走到i+1点（此转移不会导致漏解，如果第一人走到i+2，则可由第二人可走到i+1，以此类推）。所以，f(i)(j)只能转移到f(i+1)(j)（第一个人走到i+1）、f(i+1)(i)（第二个人走到i+1）。则f(i)(j)=min{f(i+1)(j)+dist(i)(i+1),f(i+1)(i)+dist(j)(i+1)}（dist(i)(j)表示点i与点j之间的距离）。边界：f(n-1)(j)（即最后一步）=dist(n-1)(n)（最后一步直接从n-1到n）+dist(j)(n)（最后一步直接从j到n）。

#include<set>#include<map>#include<cstdio>#include<cmath>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=1000+50;const int INF=0x3f3f3f3f;int n;int x[maxn],y[maxn];double f[maxn][maxn];double dist[maxn][maxn];void getDist(){    for(int i=1; i<=n; i++)    {        for(int j=1; j<=n; j++)        {            dist[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));        }    }}double solve(int i,int j){    if(f[i][j]!=INF) return f[i][j];    return f[i][j]=min(solve(i+1,j)+dist[i][i+1],solve(i+1,i)+dist[j][i+1]);}int main(){    while(scanf("%d",&n)!=EOF)    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)                f[i][j]=INF;        }        for(int i=1; i<=n; i++)            scanf("%d%d",&x[i],&y[i]);        getDist();        for(int i=1; i<n-1; i++)            f[n-1][i]=dist[n-1][n]+dist[i][n];        printf("%.2f/n",solve(1,1));    }    return 0;}