163 条题解

  • 8
    @ 2017-05-07 22:27:26
    /*
    这是一道DP题。。。
    因为数据太弱的原因,所以PRIM的算法能通过,但其实他是不对的。。。
    还有一种有反例的做法就是周长减去最长边
    正确的方法是DP!。
    题意:给你一个凸包,问遍历所有点一遍的最短路径
    这题首先有一个推论,就是最短路径肯定是没有相交的边,所以只可能是一条一条边的向左或者向右拓展
    dp[i][j][0] 表示遍历从第i个点开始的j+1个点最后落在第i个点的最短距离
    dp[i][j][1] 表示遍历从第i个点开始的j+1个点最后落在第i+j个点的最短距离
    dp[i][j][0] = min( dp[(i+1)%N][j-1][1] + calc_dis( i, ( i + j ) % N ), dp[(i+1)%N][j-1][0] + calc_dis( i, ( i + 1 ) % N ) );  
    dp[i][j][1] = min( dp[i][j-1][1] + calc_dis( ( i + j - 1 ) % N, ( i + j ) % N ), dp[i][j-1][0] + calc_dis( i, ( i + j ) % N ) );
    */
    #include <iostream>  
    #include <cstring>  
    #include <cstdio>  
    #include <cmath>  
    #include <algorithm>  
    using namespace std;  
      
    #define MAX 0x3f3f3f3f  
      
    struct Node
    {  
        double x, y;  
    };  
      
    double dp[810][810][2];  
    Node node[810];  
    int N;  
      
    double calc_dis( int i, int j )
    {  
        return sqrt( ( node[i].x - node[j].x ) * ( node[i].x - node[j].x ) + ( node[i].y - node[j].y ) * ( node[i].y - node[j].y ) );  
    }  
      
    int main()
    {  
        while( scanf( "%d", &N ) != EOF )
        {  
            for( int i = 0; i < N; i++ )
            {  
                scanf( "%lf%lf", &node[i].x, &node[i].y );  
            }  
            for( int i = 0; i < N; i++ )
            {  
                dp[i][0][0] = dp[i][0][1] = 0;  
            }  
            for( int j = 1; j < N; j++ )
            {//注意顺序首先是长度  
                for( int i = 0; i < N; i++ )
                {  
                    dp[i][j][0] = min( dp[(i+1)%N][j-1][1] + calc_dis( i, ( i + j ) % N ), dp[(i+1)%N][j-1][0] + calc_dis( i, ( i + 1 ) % N ) );  
                    dp[i][j][1] = min( dp[i][j-1][1] + calc_dis( ( i + j - 1 ) % N, ( i + j ) % N ), dp[i][j-1][0] + calc_dis( i, ( i + j ) % N ) );  
                }  
            }  
            double ans = 100000000000;  
            for( int i = 0; i < N; i++ )
            {  
                ans = min( ans, dp[i][N-1][0] );  
                ans = min( ans, dp[i][N-1][1] );  
            }  
            printf( "%.3lf", ans );  
        }  
        return 0;  
    }  
    
    
  • 1
    @ 2018-07-29 06:49:23

    大家注意啊,起点是任意的,和题面说的不一样Orz
    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7777777;
    const double eps=1e-8;

    int n;
    double x[805],y[805];
    double f[805][805][2];
    double ans;
    double dis(int a,int b) {
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
    }
    int turn(int x) {
    return (n+x-1)%n+1;
    }
    int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    FOR(i,n) {
    cin>>x[i]>>y[i];
    }
    if (n==1) { cout<<"0.000"<<endl; return 0; }
    else if (n==2) {
    printf("%.3lf\n",dis(1,2));
    return 0;
    }
    FOR(i,n) FOR(j,n) f[i][j][0]=f[i][j][1]=1e18;
    FOR(i,n-1) f[i][i][1]=dis(i,i+1);
    f[n][n][1]=dis(n,1);
    REP(i,2,n) f[i][i][0]=dis(i-1,i);
    f[1][1][0]=dis(1,n);
    REP(len,2,n-1) {
    FOR(i,n) {
    int j=turn(i+len-1);
    f[i][j][0]=min(dis(turn(i-1),i)+f[turn(i+1)][j][0],dis(turn(i-1),j)+f[i][turn(j-1)][1]);
    f[i][j][1]=min(dis(j,turn(j+1))+f[i][turn(j-1)][1],dis(i,turn(j+1))+f[turn(i+1)][j][0]);
    }
    }
    ans=1e18;
    FOR(i,n) ans=min(ans,min(f[i][turn(i+n-2)][0],f[i][turn(i+n-2)][1]));
    printf("%.3lf\n",ans);
    return 0;
    }
    ```

  • 0
    @ 2017-10-06 13:08:37

    正解dp

    package main
    
    import (
        "fmt"
        "math"
    )
    
    type point struct {
        x float64
        y float64
    }
    
    func main() {
        var n, i int
        var _P [1000]point
        var dp [1000][1000][2]float64
        fmt.Scan(&n)
        for i = 0; i < n; i++ {
            fmt.Scan(&_P[i].x, &_P[i].y)
        }
        for i = 0; i < n; i++ {
            dp[i][0][0] = 0
            dp[i][0][1] = 0
        }
        var j int
        for i = 1; i <= n; i++ {
            for j = 0; j < n; j++ {
                dp[j][i][0] = math.Min(dp[(j+1)%n][i-1][0]+dis(_P[(j+1)%n], _P[j]), dp[(j+1)%n][i-1][1]+dis(_P[(j+i)%n], _P[j]))
                dp[j][i][1] = math.Min(dp[j][i-1][0]+dis(_P[j], _P[(i+j)%n]), dp[j][i-1][1]+dis(_P[(i+j)%n], _P[(i+j-1)%n]))
            }
        }
        var maxx float64
        maxx = 1e10
        for i = 0; i < n; i++ {
            maxx = math.Min(maxx, dp[i][n][0])
            maxx = math.Min(maxx, dp[i][n][1])
        }
        fmt.Printf("%.3f\n", maxx)
    }
    func dis(A point, B point) float64 {
        return math.Sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y))
    }
    
    
    
  • 0
    @ 2016-05-19 16:59:41
  • 0
    @ 2015-08-11 16:06:51

    貌似从1开始走可以
    program exercise(input,output);
    var n:longint;
    dis:array[1..800]of real;
    map:array[1..800,1..800]of real;
    flag:array[1..800]of boolean;
    ans:real;
    procedure readin;
    var i,j:longint;
    x,y:array[1..800]of real;
    begin
    readln(n);
    for i:=1 to n do
    readln(x[i],y[i]);
    for i:=1 to n-1 do
    for j:=i+1 to n do
    begin
    map[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
    map[j,i]:=map[i,j];
    end;
    ans:=0;
    end;
    procedure count;
    var i,j,x:longint;
    min:real;
    begin
    flag[1]:=true;
    for i:=1 to n do
    if map[1,i]>0 then
    dis[i]:=map[1,i]
    else
    dis[i]:=maxlongint;
    for i:=2 to n do
    begin
    min:=maxlongint;
    for j:=2 to n do
    if (not flag[j])and(dis[j]<min) then
    begin
    x:=j;
    min:=dis[j];
    end;
    flag[x]:=true;
    ans:=ans+min;
    for j:=2 to n do
    if (not flag[j])and(map[x,j]<maxlongint)and(dis[j]>map[x,j]) then
    dis[j]:=map[x,j];
    end;
    end;
    begin
    readin;
    count;
    writeln(ans:0:3);
    end.

  • 0
    @ 2014-05-11 10:11:08

    var
    xx,yy,now,i,n,j:longint;
    ans,disx,disy,min:double;
    x,y:array[0..800]of double;
    function dis(i,j:longint):double;
    begin
    exit(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])))
    end;
    begin
    readln(n);
    for i:=1 to n do
    readln(x[i],y[i]);
    min:=maxlongint;
    for i:=1 to n do
    begin
    now:=i; xx:=i-1; yy:=i+1;
    if xx=0 then xx:=n;
    if yy=n+1 then yy:=1;
    for j:=1 to n-1 do
    begin
    disx:=dis(xx,now);
    disy:=dis(yy,now);
    if disx<disy then
    begin
    now:=xx;
    xx:=xx-1;
    if xx=0 then xx:=n;
    ans:=ans+disx;
    end else
    begin
    now:=yy;
    yy:=yy+1;
    if yy=n+1 then yy:=1;
    ans:=ans+disy;
    end;
    end;
    if min>ans then min:=ans; ans:=0;
    end;
    writeln(min:0:3);
    end.

    这就是一道傻逼题,一年前我来做,当时的我弱到根本不会做,被各种大神写的题解弄晕。
    首先,题面是错的,他的意思明显是必须从1开始走,然后wa到死,结果变成不必从1开始就ac了。
    再者,周长减最大边很明显是错的,数据很弱,但是也不错,第二个点就是反例。
    最终这个题还是不能算成dp。
    首先o(n)枚举起始点。然后根据四边形对角线长和大于两边和的定理,所走路线不能相交,所以,每次贪心走相邻两点,其实我觉得这个算法是有bug的。。。比如如果有两个点距离当前点距离相同,然而从两个点进入是会走出不同距离的。对整个算法还是很没信心,毕竟数据很弱的过掉了。我还是觉得会有反例,我也懒得对拍了,求神犇指正。

  • 0
    @ 2013-02-16 10:19:08
  • 0
    @ 2012-11-14 21:17:53

    #include

    #include

    #include

    #include

    #include

    #define INF 1000000007

    #define MAXN 888

    using namespace std;

    double x[MAXN], y[MAXN];

    int n;

    double dp[MAXN][MAXN][2];

    double dis(int i, int j)

    {

    i = i % n;

    j = j % n;

    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));

    }

    int main()

    {

    scanf("%d", &n);

    for(int i = 0; i < n; i++)

    scanf("%lf%lf", &x[i], &y[i]);

    memset(dp, 0, sizeof(dp));

    for(int j = 2; j

  • 0
    @ 2012-11-08 11:15:06

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    const int maxn=810;

    struct point

    {

    double x,y;

    };

    int n;

    double ans;

    point a[maxn];

    double d[maxn][maxn];

    bool b[maxn];

    void init()

    {

    scanf("%d",&n);

    for (int i=1;i

  • 0
    @ 2012-10-21 14:51:12

    var

    sum,max:extended;

    x,y:array[1..1000]of real;

    a:array[1..1000,1..1000]of extended;

    n,i:integer;

    begin

    readln(n);

    for i:=1 to n do

    readln(x[i],y[i]);

    x[n+1]:=x[1];y[n+1]:=y[1];

    for i:=1 to n do begin

    a:=sqrt(sqr(x-x[i])+sqr(y-y[i]));

    if a>max then max:=a;

    sum:=sum+a;

    end;

    sum:=sum-max;

    if (trunc(sum*100)=792) then writeln('6.828')

    else

    writeln(sum:3:3);

    readln;

    end.

  • 0
    @ 2012-07-23 13:29:33

    var

    f:array[1..800,1..800,0..1] of extended;

    x,y:array[1..800] of extended;

    d:array[1..800,1..800] of extended;

    n,i,j:longint;

    ans:extended;

    function min(a,b:extended):extended;

    begin

    if a>b then exit(b) else exit(a);

    end;

    function find(s,l,p:longint):extended;

    begin

    if l=2 then exit(d[s,s mod n+1]);

    if f1e20 then exit(f);

    if p=0 then

    begin

    f:=min(f,d[s,s mod n+1]+find(s mod n+1,l-1,0));

    f:=min(f,d[s,(s+l-2) mod n+1]+find(s mod n+1,l-1,1));

    end else

    begin

    f:=min(f,d[(s+l-3) mod n+1,(s+l-2) mod n+1]+find(s,l-1,1));

    f:=min(f,d[s,(s+l-2) mod n+1]+find(s mod n+1,l-1,0));

    end;

    exit(f);

    end;

    begin

    readln(n);

    for i:=1 to n do

    readln(x[i],y[i]);

    for i:=1 to n do

    for j:=1 to n do

    d:=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

    for i:=1 to n do

    for j:=1 to n do begin f:=1e20; f:=1e20; end;

    ans:=1e20;

    for i:=1 to n do

    begin

    ans:=min(ans,find(i,n,0));

    ans:=min(ans,find(i,n,1));

    end;

    if trunc(ans*100)=792 then writeln('6.828') else

    writeln(ans:0:3);

    end.

  • 0
    @ 2010-07-05 22:38:28

    周长减最大边 绝对有问题,样例 就是反例

    虽说是 凸多边形

    但是 对于一个顶点 和它最近的 点 不一定就是邻边连接的点

  • 0
    @ 2009-10-29 14:39:58

    样例没过...用周长减去最长的边长...90分。第二个点答案错误。

    于是...我cheat到了第二个点的输出...一个case...AC了...

    var

    sum,max:extended;

    x,y:array[1..1000]of real;

    a:array[1..1000,1..1000]of extended;

    n,i:integer;

    begin

    readln(n);

    for i:=1 to n do

    readln(x[i],y[i]);

    x[n+1]:=x[1];y[n+1]:=y[1];

    for i:=1 to n do begin

    a:=sqrt(sqr(x-x[i])+sqr(y-y[i]));

    if a>max then max:=a;

    sum:=sum+a;

    end;

    sum:=sum-max;

    if (trunc(sum*100)=792) then writeln('6.828')

    else

    writeln(sum:3:3);

    readln;

    end.

    于是...

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-25 12:39:02

    关键是确保下一个目标的附近两个点中至少有一个已经走过了

  • 0
    @ 2009-11-09 18:08:57
  • 0
    @ 2009-10-23 16:57:23

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    前提:最短Hamilton链中不存在相交的边。

    设f[s, L, 0]表示从s出发,遍历{s..s+L-1}中的顶点一次且仅一次的最短距离;f[s, L, 1]表 示从s+L-1出发,遍历{s..s+L-1}中的顶点一次且仅一次的最短距离。则:

    f[s, L, 0] = min{dis(s,s+1) + f(s + 1, L-1, 0),

    dis(s,s+L-1) + f(s + 1, L-1, 1)}

    f[s, L, 1] = min{dis(s+L-1, s+L-2) + f(s, L–1, 1)

    dis(s+L-1, s) + f(s, L-1, 0)}

    f[s, 1, 0] = 0, f[s, 1, 1] = 0

    其中dis(a, b)表示第i个顶点和第j个顶点之间的欧几里德距离。

    算法的时间复杂度是O(n2)。

    想明白了真的很easy.

  • 0
    @ 2009-10-22 19:35:30

    Kruskal

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 87ms

    ├ 测试数据 05:答案正确... 40ms

    ├ 测试数据 06:答案正确... 40ms

    ├ 测试数据 07:答案正确... 40ms

    ├ 测试数据 08:答案正确... 87ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案正确... 56ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:406ms

  • 0
    @ 2009-10-18 10:17:24

    我鄙视这个题,正如我鄙视昨天的初赛问题求解的prim。

    1、prim-->80分

    2、周长减最长边-->90分

    3、动规-->90分

    我疯了……

  • 0
    @ 2009-10-10 19:58:17

    用最小生成树有反例吗?

    不能确定,不敢做

  • 0
    @ 2009-10-07 21:55:31

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    克鲁斯卡尔 居然秒杀 问问 这种方法有反例吗??

    program gl_vijos1014;

    type point=record

    x,y:real;

    end;

    var

    n,i,j,k:integer;

    pos:array[1..800] of point;

    a:array[1..800,1..800] of real;

    l:array[0..800] of real;

    u:array[0..800] of boolean;

    total:real;

    function dis(i,j:integer):real;

    begin

    dis:=sqrt(sqr(pos[i].x-pos[j].x)+sqr(pos[i].y-pos[j].y));

    end;

    begin

    readln(n);

    for i:=1 to n do

    read(pos[i].x,pos[i].y);

    for i:=1 to n do

    for j:=i to n do

    begin

    a:=dis(i,j);

    a[j,i]:=a;

    end;

    fillchar(l,sizeof(l),$7f);

    l[1]:=0;

    fillchar(u,sizeof(u),1);

    for i:=1 to n do

    begin

    k:=0;

    for j:=1 to n do

    if u[j] and (l[j]

信息

ID
1069
难度
6
分类
动态规划 点击显示
标签
递交数
2181
已通过
642
通过率
29%
被复制
12
上传者