• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            PKU1925 Spiderman 【DP】

            Posted on 2007-04-05 20:41 oyjpart 閱讀(2326) 評論(2)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            Spiderman
            Time Limit:5000MS  Memory Limit:65536K
            Total Submit:1762 Accepted:197

            Description
            Dr. Octopus kidnapped Spiderman's girlfriend M.J. and kept her in the West Tower. Now the hero, Spiderman, has to reach the tower as soon as he can to rescue her, using his own weapon, the web.

            From Spiderman's apartment, where he starts, to the tower there is a straight road. Alongside of the road stand many tall buildings, which are definitely taller or equal to his apartment. Spiderman can shoot his web to the top of any building between the tower and himself (including the tower), and then swing to the other side of the building. At the moment he finishes the swing, he can shoot his web to another building and make another swing until he gets to the west tower. Figure-1 shows how Spiderman gets to the tower from the top of his apartment – he swings from A to B, from B to C, and from C to the tower. All the buildings (including the tower) are treated as straight lines, and during his swings he can't hit the ground, which means the length of the web is shorter or equal to the height of the building. Notice that during Spiderman's swings, he can never go backwards.


            You may assume that each swing takes a unit of time. As in Figure-1, Spiderman used 3 swings to reach the tower, and you can easily find out that there is no better way.

             

            Input
            The first line of the input contains the number of test cases K (1 <= K <= 20). Each case starts with a line containing a single integer N (2 <= N <= 5000), the number of buildings (including the apartment and the tower). N lines follow and each line contains two integers Xi, Yi, (0 <= Xi, Yi <= 1000000) the position and height of the building. The first building is always the apartment and the last one is always the tower. The input is sorted by Xi value in ascending order and no two buildings have the same X value.

            Output
            For each test case, output one line containing the minimum number of swings (if it's possible to reach the tower) or -1 if Spiderman can't reach the tower.

            Sample Input

            2
            6
            0 3
            3 5
            4 3
            5 5
            7 4
            10 4
            3
            0 3
            3 4
            10 4
            

             

            Sample Output

            3
            -1
            

             

            Source
            Beijing 2004 Preliminary@POJ

            這是DP題,根據坐標DP是比較好的選擇,提交中wa多次。經回復指點 才注意到建筑物高度相乘越界了 謝謝提醒了

            //Solution by oyjpArt
            #include <stdio.h>
            #include <math.h>
            #include <string.h>
            const int N = 5010;
            const int M = 1000010;
            int x[N], y[N], dp[M], nb;
            const int MAXINT = 2000000000;
            #define Min(a,b) ((a) < (b) ? (a) : (b))

            int main() {
             int ntc, i, j;
             scanf("%d", &ntc);
             while(ntc--) {
              scanf("%d", &nb);
              for(i = 0; i<nb; i++)  scanf("%d %d", x+i, y+i);
              int m = x[nb-1];
              memset(dp, -1, (m+1)*sizeof(dp[0]));
              dp[x[0]] = 0;
              double h = y[0]; 
              for(i = 1; i<nb; i++) { //以1..i的建筑為中介進行飛行
               int d = sqrt(2*y[i]*h - h*h); //不會墜落到地上的最長距離 sqrt(y[i]*y[i]-sqare(y[i]-h))
               for(j = 1; j<=d; j++) { //DP
                if(x[i]-j < x[0]) break; //無用狀態
                if(dp[x[i]-j] == -1) continue; //不可達
                int k = x[i]+j < m ? x[i]+j : m;
                if(dp[k] == -1) dp[k] = dp[x[i]-j]+1;
                else dp[k] = Min(dp[k], dp[x[i]-j]+1);
               }//for
              }//for
              printf("%d\n", dp[m]);
             }
             return 0;
            }

            Feedback

            # re: PKU1925 Spiderman 【DP】  回復  更多評論   

            2007-04-11 15:24 by mark
            int的話相乘后可能越界了

            # re: PKU1925 Spiderman 【DP】  回復  更多評論   

            2007-04-16 20:53 by oyjpart
            謝謝提醒 呵呵
            国产毛片欧美毛片久久久| 香蕉久久永久视频| 无遮挡粉嫩小泬久久久久久久| 四虎国产精品成人免费久久 | 一本久道久久综合狠狠爱| 久久亚洲AV成人无码| 国产精品久久久久jk制服| 久久狠狠爱亚洲综合影院| 欧美日韩精品久久免费| 久久精品国产网红主播| 欧美日韩中文字幕久久久不卡| 久久99热这里只有精品66| 久久婷婷五月综合色高清| 久久精品无码免费不卡| 久久国产精品77777| 热RE99久久精品国产66热| 72种姿势欧美久久久久大黄蕉| 久久国产精品免费一区| 久久99国内精品自在现线| 香蕉久久永久视频| 日韩久久无码免费毛片软件| 蜜桃麻豆www久久| 久久男人Av资源网站无码软件| 中文字幕久久精品| 国产日韩欧美久久| 国产精品青草久久久久福利99| 97热久久免费频精品99| 无码人妻精品一区二区三区久久久 | 久久久久无码中| 99精品久久精品一区二区| 久久久高清免费视频| 亚洲国产成人精品久久久国产成人一区二区三区综| 婷婷久久久亚洲欧洲日产国码AV| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 国产精品久久久久jk制服| 久久精品国产AV一区二区三区| 精品无码人妻久久久久久| 精品久久人人妻人人做精品| 91超碰碰碰碰久久久久久综合| 国产L精品国产亚洲区久久 | 色综合久久久久久久久五月 |