122 条题解

  • 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

    貌似坐标是小数

  • 0
    @ 2009-09-05 14:33:18

    封人号SB

  • 0
    @ 2009-09-01 20:09:01

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

    方程不难,但是数组开小了 Orz………………

    没秒杀是个遗憾。

  • 0
    @ 2009-08-30 11:12:19

    日,点的坐标居然可以不是整数

    害得我WA一次

  • 0
    @ 2009-08-25 10:45:16

    点的坐标不是整数

  • 0
    @ 2009-08-15 11:41:53

    var

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

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

    n:longint;

    function dist(k1,k2:longint):real;

    begin

    dist:=sqrt(sqr(a[k1]-a[k2])+sqr(b[k1]-b[k2]));

    end;

    procedure dp;

    var

    i,j,k:longint;

    temp:real;

    begin

    for i:=1 to n-1 do

    for j:=i+1 to n do

    if a[i]>a[j] then

    begin

    temp:=a[i];a[i]:=a[j];a[j]:=temp;

    temp:=b[i];b[i]:=b[j];b[j]:=temp;

    end;

    for i:=1 to n do

    for j:=1 to n do f[i][j]:=1e24;

    f[2][1]:=dist(1,2);

    for i:=1 to n do

    for j:=1 to n do

    begin

    if i>j+1 then f[i][j]:=f[j]+dist(i-1,i);

    if i=j+1 then for k:=1 to i-2 do

    if f[i][j]>f[k]+dist(k,i) then f[i][j]:=f[k]+dist(k,i);

    end;

    f[n][n]:=1e24;

    for i:=1 to n-1 do

    if f[n][n]>f[n][i]+dist(i,n) then f[n][n]:=f[n][i]+dist(i,n);

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

    end;

    procedure init;

    var

    i:longint;

    begin

    readln(n);

    for i:=1 to n do readln(a[i],b[i]);

    end;

    begin

    init;

    dp;

    end.

    题目输入有问题。。。是实数 而不是整型。。。。

  • 0
    @ 2009-08-11 20:46:00

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    数据有点弱,还以为要用double

    方程和各位差不多

  • 0
    @ 2009-08-11 18:08:53

    这道题的动归方程很巧妙:

    方程:f=min{f+d,f+d};{i

  • 0
    @ 2009-08-05 10:35:00

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-08-02 11:10:38

    想了好久终于想明白了....

    结果因为快排一个变量打错,交N次....

  • 0
    @ 2009-07-21 13:16:02

    双进程DP的模型大多这样:

    F 表示 第1个人走到i,第2个人走到J的最短路程

    此题数据够弱,

    1.同一直线上的情况没考虑都AC

    2.有可能没有回路,但是数据没有这种情况

  • 0
    @ 2009-07-09 14:58:58

    var i,j,n:integer;

    s,t:real;

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

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

    procedure quick(s,t:integer);

    var i,j:integer;

    z1,z2:real;

    begin

    z1:=x[(s+t) div 2];

    z2:=y[(s+t) div 2];

    x[(s+t) div 2]:=x;

    y[(s+t) div 2]:=y;

    x:=z1;

    y:=z2;

    i:=s;

    j:=t;

    while i

  • 0
    @ 2009-07-09 13:24:01

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    秒杀

    动规方程:

    F表示I点开始返回到I-1点的最小路径

    则 F=MAX(F[J+1]+D+DIS)

  • 0
    @ 2009-11-09 21:30:46

    var

    i,j,k,l,m,n,z:Longint;

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

    a:array[0..1000] of record

    x,y:Longint;

    end;

    qq:array[0..1000] of real;

    dis:array[0..1000,0..1000] of real;

    procedure pai(l,r:longint);

    var

    i,j,k,m:Longint;

    begin

    i:=l;

    j:=r;

    k:=a[i].x;

    m:=a[i].y;

    while i

  • 0
    @ 2009-07-06 22:51:08

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    const int MaxN = 1000 + 10;

    struct node

    {

    int x, y;

    }a[MaxN];

    int n;

    double dp[MaxN][MaxN];

    bool cmp(const node& a, const node& b)

    {

    return a.x < b.x;

    }

    #define sqr(a) ((a) * (a))

    #define dist(a, b) (sqrt(double(sqr(double(a.x - b.x)) + sqr(double(a.y - b.y)))))

    int main()

    {

    cin >> n;

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

    cin >> a[i].x >> a[i].y;

    sort(a, a + n, cmp);

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

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

    dp[i][j] = 1e60;

    dp[0][0] = 0;

    int i,j;

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

    for (j = 0; j < n; ++j)

    {

    int t = min(n - 1, max(i, j) + 1);

    dp[i][t] = min(dp[i][t], dp[i][j] + dist(a[j], a[t]));

    dp[t][j] = min(dp[t][j], dp[i][j] + dist(a[i], a[t]));

    }

    printf("%.2lf\n", dp[n - 1][n - 1]);

    return 0;

    }

    比较暴力,还算短

  • 0
    @ 2009-07-02 15:43:47

    要求是双调路径。。

  • 0
    @ 2009-06-15 22:42:33

    这个题首先要拆成两个人,看成是分别走,路径没有重复的最短路。

    这个题如果设f表示第一个人到i,第二个人到j的最短路,很容易设计出一个O(n^3)的方法,可惜会超时。

    这个题有一个特点,就是所有点之间都可以互相到达,而且距离跟拓扑序列几乎成正比。于是就诞生了一个O(n^2)的算法。每次计算f时,显然只需要计算i>=j的情况就可以了。此时,考虑最后的一步。

    有两种情况

    1. 从j-1走到i,此时就和状态f[j,j-1]有关。

    2. 从j-1走到j,此时就和状态f有关。

    也许有的人会认为可能是从i-1走到i,这种情况不能考虑!!对于前面的点,如果你考虑了i-1到i的情况,你无法保证j走不到i-1,也就是保证不了没有后效性,因为j的走法不是当前状态能决定的!!但是如果j-1到j的话,f已经是一个固定的状态,,不会再有点走到j-1!!所以没有问题!!于是,每次走的时候,为了保证没有后效性,前面的一个人必须从后面的人在后面的点飞过去,相当于枚举了初始点。这样就只剩下了两种转移,一种是后面的人一步一步走,另一种是前面的人飞过去。

  • 0
    @ 2009-04-27 18:16:09

    能否来个C的DP,说的不是很懂 来份代码

  • 0
    @ 2009-04-26 22:22:00

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    坐标也要用实行,长整型要挂掉!!!

    坐标也要用实行,长整型要挂掉!!!

    坐标也要用实行,长整型要挂掉!!!

    坐标也要用实行,长整型要挂掉!!!

    坐标也要用实行,长整型要挂掉!!!

    var i,j,n:integer;

    s,t:real;

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

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

    procedure quick(s,t:integer);

    var i,j:integer;

    z1,z2:real;

    begin

    z1:=x[(s+t) div 2];

    z2:=y[(s+t) div 2];

    x[(s+t) div 2]:=x;

    y[(s+t) div 2]:=y;

    x:=z1;

    y:=z2;

    i:=s;

    j:=t;

    while i

  • 0
    @ 2009-03-25 19:39:52

    NEW WAY---

    可转化为最小费用最大流模型解决!

    时空复杂度不错,只是编程复杂度嘛~~

    还是用DP啦.

    ( 2007-11-12 15:06:13 ah_gj)

    ...

    我又看到班班的留言了...哎..为什么不留下来呢...

    我们这么迟都没有解决这题...最近才知道最小费用流..#

    ...真是惭愧..

    #24...这题可以用最小费用流作么?..

    是不是应该比较一下这题..?

    http://www.nocow.cn/index.php/Translate:USACO/tour

信息

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