UVa 1347 旅行

思路:用d(i,j)表示第一个人走到i，第二个人走到j，还需要走多长的距离。在这里强制定义i>j，并且每次只能走到i+1。

状态转移方程为:d(i,j)=min(d(i+1,j)+dist(i,i+1),d(i+1,i)+dist(j,i+1));

仿照紫书“硬币问题”的代码，可以写成如下形式:

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 const int maxn=1000+5;
 8 
 9 int n;
10 
11 struct node
12 {
13     int x, y;
14 }a[maxn];
15 
16 double d[maxn][maxn];   //第一个走到i，第二个人走到j,d[i][j]表示此时还需要走多长的距离
17 
18 
19 double dist(int i,int j)
20 {
21     int dx = a[i].x - a[j].x;
22     int dy = a[i].y - a[j].y;
23     return hypot(dx, dy);  //计算直角三角形的斜边
24 }
25 
26 double dp(int i, int j)  //i一定大于j
27 {
28     double& ans = d[i][j];
29     if (ans > 0)  return ans;
30     if (i == n - 1)
31         return ans=dist(i, n) + dist(j, n);
32     ans = min(dp(i + 1, j) + dist(i + 1, i), dp(i + 1, i) + dist(i + 1, j));
33     return ans;
34 }
35 
36 int main()
37 {
38     //freopen("D:\txt.txt", "r", stdin);
39     while (cin >> n && n)
40     {
41         memset(d, 0, sizeof(d));
42         for (int i = 1; i <= n; i++)
43         {
44             cin >> a[i].x >> a[i].y;
45         }
46         dp(2, 1);
47         double ans = dist(2, 1) + d[2][1];
48         printf("%.2f
", ans);
49     }
50     return 0;
51 }