首页 > ACM题库 > HDU-杭电 > HDU 3322-The Flowers Floating On The YueYa Lake-数论-[解题报告]HOJ
2014
03-16

HDU 3322-The Flowers Floating On The YueYa Lake-数论-[解题报告]HOJ

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)时间的算法。

The Flowers Floating On The YueYa Lake
注:在一个单位栅格上显示的平面上的七个点。

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

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

相关的题目有很多:如NOIP的三取方格数、传纸条、CLRS思考题15-1、HDU3322。

下面是HDU3322

将各个节点从左至右进行排序,编号为1,2,….n。令dp[i][j](i>j)表示去的路和回的路的较长者在i点,另一个在j点处的最短双调路线。

如图:The Flowers Floating On The YueYa Lake
那么显然有:

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又成了较长者

最后答案为min(dp[n][i]+dis(i,n)),dp[n][i]表示一条路走到了n,另一条路走到比n小的某个点i的最短路径,再加上i点到n点的距离即为答案。

代码:

#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);
    }
}

附两个算法LINK:

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

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

参考:http://hi.baidu.com/matrush/item/bcf51a12ed22a743e65e0636


  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猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……