2014
03-16

The Flowers Floating On The YueYa Lake

We all know the YueYa Lake of HDU. It is very beautiful, especially in the evening. However, most of HDU’s ACMers may not know,because they only know where the apartments and the laboratory are and they often get lost when they go to other places even Canteen.

CR was very excited when he knew Spring Festival is Valentine’s Day this year. Finally, that day is coming. He pulled out the map of HDU and then walked towards the direction of the YueYa Lake.He knew that today there would be a lot of beautiful MMs. Soon, he arrived and he was so lucky that he met a beautiful girl. The girl told him that she would like to have all the flowers floating on the water of YueYa Lake. She also told him if he fulfilled her this wish she was willing to be his girlfriend! How exciting!

Simply，we can see each of flowers as a point (Pi(xi, yi), 0<xi,yi, i≠j,xi≠xj) in the plane and CR stand at coordinate origin.CR must get all the flowers floating in the water and then go back to coordinate origin.Although our CR knew a little Kungfu of QingKung, it’s also a hard work, because it’s would cost CR |PiPj| calories of energy when he flew from Pi to Pj. Our small CR want to make it a wonderful thing that he spent the least energy. But there is a rule:

Before you reach the rightmost point , you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can visit Pj only when xj>xi. But when you reach the rightmost point, the rule has changed, you can only visit the points those have the smaller x-coordinate value than the point you are at now.For example, you are at Pi now, then you can visit Pj only when xj<xi.

Of course CR knew the answer, but what about you, clever ACMers?

Input consists of multiple test cases. Each case begins with a line containing a positive integer n(0 < n <= 500), means the number of points. Then following n lines each containing two positive integers Pi(xi, yi), indicating the coordinate of the i-th point in the plane.
A test case with n = 0 terminates the input and this test case is not to be processed.

Input consists of multiple test cases. Each case begins with a line containing a positive integer n(0 < n <= 500), means the number of points. Then following n lines each containing two positive integers Pi(xi, yi), indicating the coordinate of the i-th point in the plane.
A test case with n = 0 terminates the input and this test case is not to be processed.

3
1 1
2 3
3 1
0

9.05

Hint
The path (0,0) - (3,1) - (2,3) - (1,1) - (0,0) makes the least energy.

HDU3322-The Flowers Floating On The YueYa Lake，在lcc大牛的题解和指导下AC，那个利用对称性交换下标太强了。

欧几里得旅行商问题是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题。如图（a）给出了一个7个点问题的解。这个问题的一般形式是NP完全的，故其解需要多于多项式的时间。

J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下，多项式的算法是可能的。事实上，存在确定的最优双调路线的O(n*n)时间的算法。

(a):最短闭合路线,长度大约是24.89。这个路线不是双调的。

(b):相同点的集合上的最短双调闭合路线。长度大约是25.58。

dp[i+1][j] = min(dp[i+1][j],dp[i][j] + dis(i,i+1));//i点走到i+1点，i+1显然为较长者
dp[i+1][i] = min(dp[i+1][i],dp[i][j] + dis(j,i+1));//j点走到i+1点，i+1又成了较长者

#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 501;
struct data { double x,y;
}p[MAXN];
inline double sqr(double x)
{
return x * x;
}
double dis(int a,int b)
{
return sqrt(sqr(p[a].x – p[b].x) + sqr(p[a].y – p[b].y));
}
bool cmp(data a,data b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int main()
{
int n;
double dp[MAXN][MAXN];
while (scanf("%d",&n) != EOF && n)
{
for (int i = 1;i <= n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p,p+n+1,cmp);
memset(dp,0,sizeof(dp));
for (int i = 0;i <= n;i++)
for (int j = 0;j <= n;j++)
dp[i][j] = 1e20;
dp[0][0] = 0;
for (int i = 0;i < n;i++)
for (int j = 0;j <= i;j++)
{
dp[i+1][j] = min(dp[i+1][j],dp[i][j] + dis(i,i+1));
dp[i+1][i] = min(dp[i+1][i],dp[i][j] + dis(j,i+1));
}
double ans = 1e20;
for (int i = 0;i <= n;i++)
{
if (dp[n][i] + dis(i,n) < ans)
ans = dp[n][i] + dis(i,n);
}
printf("%.2lf\n",ans);
}
}

http://blog.sina.com.cn/s/blog_41630e7e0100dp4o.html

http://blog.sina.com.cn/s/blog_51cea4040100gkcq.html

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

3. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

4. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……