hdu 2224 The shortest path 单向旅行商问题

Problem:
有n个节点，一个人去访问这n个节点，要从最左边的节点开始，经过这n个节点后再返回源点，在达到最右边之前只能向右走，同理回来时只能向左走，同一个节点只能经过一次，问最短路是多少？
Solution：
容易知道如果我们最终的结果是最短路的话，那路线中不能有交叉点，即路线是一个环，假设dp[i][j]表示从i个起点出发，1是拐点，j是终点，且已经经过了j之前的所有节点，那么最终dp[n][n]就是我们要的结果。我们令i <= j，那么状态转换为：
i <= j-2时：dp[i][j] = dp[i][j-1] + dist(j, j-1);既然访问过j个节点，j-2个节点又在i的那一侧，那么可知j-1和j在同一侧。
i == j-1时：dp[j-1][j] = min(dp[k][j-1] + dist(k, j));既然访问过j个节点，且j-1在另一侧，那么j节点同侧的相邻的前一个节点就有可能是任意一个节点，那么我们遍历每一个节点找到这个值最小的节点。
i == j时：dp[j][j] = dp[j-1][j] + dist(j-1, j)这一步相当于将之前的U型路线闭环，而j和j-1是在最右边的两个节点，我们计算一下距离连接起来即可。

notes：
难点在于没有想到状态的转换，分情况分侧转换的这种思路，状态的定义也非常的重要。

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<vector>
#include<fstream>
#include<list>
#include<numeric>
#include<functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s,0,sizeof(s))

const double PI = 3.141592653589;
const int INF = 0x3fffffff;

double getDis(int x1, int y1, int x2, int y2) {
return sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1));
}

double dp[205][205];
int x[205], y[205];
int n;

void solve() {
    dp[1][1] = 0;
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= i-2; j++) {
            dp[j][i] = dp[j][i-1]+getDis(x[i-1],y[i-1], x[i],y[i]);
        }
for(int j = 1; j <= i-1; j++) {
            dp[i-1][i] = min(dp[i-1][i], dp[j][i-1]+getDis(x[j], y[j], x[i], y[i]));
        }
        dp[i][i] = dp[i-1][i] + getDis(x[i-1], y[i-1], x[i], y[i]);
    }
}

int main() {
// freopen("/Users/really/Documents/code/input","r",stdin);
// freopen("/Users/really/Documents/code/output","w",stdout);
        ios::sync_with_stdio(false);

while(scanf("%d", &n) != EOF) {
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
                dp[i][j] =INF;
for(int i = 1; i <= n; i++)
scanf("%d%d", &x[i], &y[i]);
        solve();
printf("%.2f\n", dp[n][n]);
    }

return 0;
}