122 条题解

  • 4
    @ 2017-05-07 12:48:00

    /*
    醉了醉了~
    这题弄了一下午一直只能过样例+第一个点
    这是为啥呢
    然后才发现INF傻逼一般地打成了int型,然后一改double瞬间AC
    悲伤的故事
    这是一道痕经典的动规问题吧
    lrj紫书上dp一章P269有~
    f[ i ][ j ]表示第一个人走到i,第二个人走到j 的最短路径,
    要求i<j,且0到j的点都被经过了(因为f[i][j]和f[j][i]等效,所以可以减少枚举)
    这样很容易想到,j+1的点不是被第一个人走,就是被第二个人走
    考虑到找前驱状态很麻烦~我们就可以找后继状态去刷新他们的值
    也就是刷表法了~~
    所以有转移方程
    f[ i ][ j+1]=min{ f[ i ] [ j ]+d[ j ] [ j +1] }
    f[ j ] [ j+1 ]=min{ f[ i ][ j ]+d[ i ][ j+1 ] }
    初值f[0][1]=d[0][1](d[i][j]表示第i个点到第j个点的距离)
    即可以发现对于某个状态来说,他可以连锁更新两个状态,
    即f[i][j+1],f[j][j+1]
    嗯第一个方程应该很好解释了
    就是第二个人走到下一个点的情况
    第二个方程可以这么理解,
    两个人可以指前面一个人,和后面一个人,
    当后面的人走到前面,当然就对换过来了,不影响结果
    即两个人是不区分的,只是一个前面一个后面,因为是等效的
    所以当后面这个人走到j+1位置的时候,那肯定会有原来走的更前的那个人
    变成了更后的那个人,即变成了f[j][j+1]
    (好好理解一下)
    这样就不难操作了,我们先预处理一下数据
    对于读进的数,我们按从横坐标从小到大排序
    然后预处理距离d[][],用勾股定理求坐标距离就好了
    注意不管是f[][]还是d[][]我们都只需要求f[i][j](i<j)即可
    然后再扫描一遍求所有状态的可能情况(不包括终点)
    我们的f[][n]表示的是前面那个人走到了n点了
    但是后面那个人还没有到n点
    如果要完成一个哈密尔
    顿回路的话就还差了后面那个人到n点的距离
    所以答案就是min{f[i][n]+d[i][n]}
    所以遍历一下这n-1种状态就好了>3<
    好题~
    */

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const double INF=1e30;
    const int MAXN=1003;
    struct node
    {
        double x,y;
        bool operator<(const node&b)const
        {
            return x<b.x;
        }
    }a[MAXN];
    int n;
    double ans=INF;
    double f[MAXN][MAXN];
    double d[MAXN][MAXN];
    
    double getd(int i,int j)
    {
        double x=fabs(a[i].x-a[j].x);
        double y=fabs(a[i].y-a[j].y);
        return sqrt(x*x+y*y);
    }
    
    void init()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i].x>>a[i].y;
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                d[i][j]=getd(i,j),f[i][j]=INF;
    }
    
    void DP()
    {
        f[1][2]=d[1][2];
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                f[i][j+1]=min(f[i][j+1],f[i][j]+d[j][j+1]);
                f[j][j+1]=min(f[j][j+1],f[i][j]+d[i][j+1]);
            }
        for(int i=1;i<=n-1;i++)  
            ans=min(ans,f[i][n]+d[i][n]);  
        printf("%.2lf\n",ans);
    }
    
    int main()
    {
        init();
        DP();
    }
    
    • @ 2018-05-26 19:55:53

      你还需要一个cmath

  • 1
    @ 2021-03-15 13:54:31

    //P1523 100pts
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define INF 1e50
    #define MAXN 1010
    #define dbl double
    using namespace std;
    struct node{
    dbl x;
    dbl y;
    bool operator<(const node &rhs)const{
    return x<rhs.x;
    }//按照纵坐标从左往右排序
    }arr[MAXN];
    int n;
    dbl f[MAXN][MAXN];
    inline dbl dis(int x,int y){
    return hypot(fabs(arr[x].x-arr[y].x),fabs(arr[x].y-arr[y].y));
    }
    int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
    scanf("%lf%lf",&arr[i].x,&arr[i].y);
    }
    sort(arr+1,arr+1+n);//排序
    // for(int i=1;i<=n;++i){
    // printf("%lf %lf\n",arr[i].x,arr[i].y);
    // }
    for(int i=0;i<=1000;++i){
    for(int j=0;j<=1000;++j){
    f[i][j]=INF;
    }
    }
    f[2][1]=dis(1,2);
    // printf("f[2][1]=%lf\n",f[2][1]);
    for(int i=3;i<=n;++i){
    for(int j=i-1;j>=1;--j){
    if(i==j+1){
    //刚好是向后一个的节点
    for(int k=j-1;k>=1;--k){
    f[i][j]=min(f[i][j],f[j][k]+dis(k,i));
    }
    }else{
    f[i][j]=min(f[i][j],f[i-1][j]+dis(i-1,i));
    }
    }
    }
    double ans=INF;
    for(int i=1;i<=n;++i){
    ans=min(ans,f[n][i]+dis(i,n));
    }
    // printf("\n");

    printf("%.2lf\n",ans);
    }

  • 1
    @ 2015-08-21 16:58:45

    参照楼上大神的代码,完成AC。在这留下c++代码

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int N = 1100;
    const int M = 150;
    double dp[N][N];
    int n,m,t;
    struct opint
    {
    double x,y;
    bool operator <(const opint &k)const
    {
    if(k.x == x)
    return y < k.y;
    else
    return x < k.x;
    }
    }s[N];
    double Dis(int a, int b)
    {
    return sqrt((s[a].x - s[b].x) * (s[a].x - s[b].x) + (s[a].y - s[b].y) * (s[a].y - s[b].y));
    }
    int main()
    {
    while(~scanf("%d",&n))
    {
    for(int i = 0; i < n; i++)
    scanf("%lf%lf",&s[i].x,&s[i].y);
    for(int i = 0; i < n; i++)
    fill(dp[i],dp[i]+n,1e60);
    sort(s,s+n);
    dp[0][0] = 0;
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
    int k = min(n-1,max(i,j) + 1);
    dp[i][k] = min(dp[i][k],dp[i][j] + Dis(j,k));
    dp[k][j] = min(dp[k][j],dp[i][j] + Dis(i,k));
    }
    printf("%.2lf\n",dp[n-1][n-1]);
    }
    }

  • 1
    @ 2009-09-27 20:17:44

    program p1014;

    type

    rec=record

    x,y:real;

    end;

    shuzu=array[0..1200] of rec;

    var

    a:shuzu;

    f:array[0..1200,0..1200] of real;

    n,i,j,k:integer;

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

    begin

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

    end;

    function min(c,d:real):real;

    begin

    if c>d then c:=d;

    min:=c;

    end;

    procedure q(var a:shuzu; l,r:integer);

    var

    i,j:integer; tp:rec; t:real;

    begin

    i:=l;

    j:=r;

    t:=a[(l+r) div 2].x;

    while i

  • 0
    @ 2020-12-12 19:05:22
    //P1523 100pts 
    #include<cmath> 
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define INF 1e50 
    #define MAXN 1010
    #define dbl double
    using namespace std;
    struct node{
        dbl x;
        dbl y;
        bool operator<(const node &rhs)const{
            return x<rhs.x;
        }//按照纵坐标从左往右排序 
    }arr[MAXN];
    int n;
    dbl f[MAXN][MAXN];
    inline dbl dis(int x,int y){
        return hypot(fabs(arr[x].x-arr[y].x),fabs(arr[x].y-arr[y].y));
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%lf%lf",&arr[i].x,&arr[i].y);
        } 
        sort(arr+1,arr+1+n);//排序
    //  for(int i=1;i<=n;++i){
    //      printf("%lf %lf\n",arr[i].x,arr[i].y);
    //  }
        for(int i=0;i<=1000;++i){
            for(int j=0;j<=1000;++j){
                f[i][j]=INF;
            }
        }
        f[2][1]=dis(1,2);
    //  printf("f[2][1]=%lf\n",f[2][1]);
        for(int i=3;i<=n;++i){
            for(int j=i-1;j>=1;--j){
                if(i==j+1){
                    //刚好是向后一个的节点
                    for(int k=j-1;k>=1;--k){
                        f[i][j]=min(f[i][j],f[j][k]+dis(k,i));
                    } 
                }else{
                    f[i][j]=min(f[i][j],f[i-1][j]+dis(i-1,i));
                }
            }
        }
        double ans=INF;
        for(int i=1;i<=n;++i){
            ans=min(ans,f[n][i]+dis(i,n));
        }
    //      printf("\n");
        
        printf("%.2lf\n",ans);
    }
    
  • 0
    @ 2018-06-21 19:04:51

    同是只过了样例和一个点,也是int inf。。。
    不过还多犯了一个错误,i和j打反了。。
    感觉这个DP很棒,维护一个曲线(可能自交),然后利用曲线长度取最小值的时候一定不会自交,一定是题目要求的那种样子,然后取一个特殊情形就是封闭成回路的情况。

  • 0
    @ 2018-05-26 19:57:15

    状态 耗时 内存占用

    #1 Accepted 6ms 2.375 MiB
    #2 Accepted 4ms 2.5 MiB
    #3 Accepted 6ms 4.734 MiB
    #4 Accepted 5ms 3.137 MiB
    #5 Accepted 14ms 10.621 MiB
    #6 Accepted 36ms 15.5 MiB
    #7 Accepted 39ms 15.5 MiB
    #8 Accepted 40ms 15.504 MiB
    #9 Accepted 37ms 15.484 MiB
    #10 Accepted 40ms 15.371 MiB

  • 0
    @ 2014-07-29 21:16:58

    初始化大一点……
    ###Block Code
    double mmin=11111111111111.0;
    rep(k,1,j){
    if(f[j][k]==-1)
    f[j][k]=dp(j,k);
    mmin=min(mmin,f[j][k]+d[i][k]);
    }

  • 0
    @ 2012-07-20 01:29:01

    这道题目纠结了我3天。。总算是弄清楚了。。

    首先要声明:数据中不存在同一个x坐标上有多于2个点的情况!

    状态的表示很容易想到。。由于只能单向前进(不管是从西向东还是从东向西)。。所以只要走过的点是不可能再在后面的规划中遇到的。。也就是说。。如果将题目考虑成同时有两个从西往东走。。那么每一个坐标点必然会**立即**加入两条路线中的一条。。于是。。我们可以用f[i][j]表示当前两条路线的最后一个点分别是i和j。。f[i][j]隐含的一个意思是:对于所有kj因为不难发现f的对称性,即f[i][j]=f[j][i]。。接下来的事情就是分析f[i][j]能够由哪些状态转移得到。。

    由于规定i>j。。故而为了维护这个性质。。新加入的点

  • 0
    @ 2009-09-30 22:50:46

    f=min{f[k,i-1]+min{dist[k,i]+dist,dist[k,j]+dist} (1

  • 0
    @ 2009-09-27 14:05:34

    编译通过...

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

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

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

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

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

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

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

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

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

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

    program ex;

    var f:array[0..1001,0..1001] of real;

    x,y:array[0..1001] of real;

    i,j,n:longint;

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

    begin

    if a>b then exit(b)

    else exit(a);

    end;

    procedure swap(var a,b:real);

    var t:real;

    begin

    t:=a;a:=b;b:=t;

    end;

    function dist(i,j:longint):real;

    begin

    exit(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])));

    end;

    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

    if x[i]>x[j] then

    begin

    swap(x[i],x[j]);

    swap(y[i],y[j]);

    end;

    for i:=2 to n do

    f:=f+dist(i,i-1);

    for i:=2 to n do

    for j:=2 to i do

    f:=min(f+dist(j,j-1),f[j,j-1]+dist(i,j-1));

    writeln(f[n,n]:0:2);

    end.

    秒杀

  • 0
    @ 2009-09-25 19:05:09

    到底是怎么给你们想到的

  • 0
    @ 2009-09-23 19:12:50

    f[i]=min(f[j]+sum[j,i]-dist[j-1,j]+dist[j-1,i])

    f[i]表示到第i个节点的最小回路。枚举由哪个点断开回路连向第i个节点。

    时间、空间O(n^2)

  • 0
    @ 2009-09-20 10:11:32

    编译通过...

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

    ├ 测试数据 02:运行时错误...|错误号: 207

    ├ 测试数据 03:运行时错误...|错误号: 207

    ├ 测试数据 04:运行时错误...|错误号: 207

    ├ 测试数据 05:运行时错误...|错误号: 207

    ├ 测试数据 06:运行时错误...|错误号: 207

    ├ 测试数据 07:运行时错误...|错误号: 207

    ├ 测试数据 08:运行时错误...|错误号: 207

    ├ 测试数据 09:运行时错误...|错误号: 207

    ├ 测试数据 10:运行时错误...|错误号: 207

    怎么回事

  • 0
    @ 2009-09-18 21:49:49
  • 0
    @ 2009-09-17 11:28:56

    program lv_you_shang_jian_hua_ban;

    const maxn=1010;

    var a,b:array[0..maxn,0..maxn]of real;

    x,y:array[0..maxn]of real;

    i,j,k,m,n,o,u,p,q:longint;

    ans:real;

    procedure sort(p,q:longint);

    var i,j:longint; g,k:real;

    begin

    i:=p; j:=q;

    k:=x[(p+q) shr 1];

    repeat

    while kx[i] do inc(i);

    if ij;

    if (p

  • 0
    @ 2009-09-20 11:48:50

    题解:

  • 0
    @ 2009-09-08 19:48:45

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    const filename='p1014';

    var

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

    f:array[1..1000,1..1000]of double;

    i,j,n:longint;

    function dist(i,j:longint):double;

    begin exit(sqrt(sqr(x[i]-x[j-1])+sqr(y[i]-y[j-1]))); end;

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

    begin if a>b then exit(b);exit(a);end;

    procedure qsort(l,r:longint);

    var i,j:longint;xx,yy:double;

    begin

    i:=l;j:=r;xx:=x[l];yy:=y[l];

    while(i

  • 0
    @ 2009-09-08 12:36:33

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    ....初始化小了晕。。害我交了3次。。。

    我的方法可能有点麻烦了。。。

    先初始化。。

    F表示第1条路到I点,第2条路到J点。

    I 1 TO N

    J 1 TO I-1

    如果 I-1>J

    直接F由F推出。

    如果I-J

    F:=MIN{F[H,J]+V[H,I]}(1〈=H〈=J-1)

    答案MAX{F[N,I]+V}(1〈=I〈N)

  • 0
    @ 2009-09-05 23:14:43

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    貌似坐标是小数

信息

ID
1014
难度
6
分类
动态规划 点击显示
标签
(无)
递交数
2899
已通过
876
通过率
30%
被复制
11
上传者