青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

// 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 閱讀(2336) 評(píng)論(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題,根據(jù)坐標(biāo)DP是比較好的選擇,提交中wa多次。經(jīng)回復(fù)指點(diǎn) 才注意到建筑物高度相乘越界了 謝謝提醒了

//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的建筑為中介進(jìn)行飛行
   int d = sqrt(2*y[i]*h - h*h); //不會(huì)墜落到地上的最長(zhǎng)距離 sqrt(y[i]*y[i]-sqare(y[i]-h))
   for(j = 1; j<=d; j++) { //DP
    if(x[i]-j < x[0]) break; //無用狀態(tài)
    if(dp[x[i]-j] == -1) continue; //不可達(dá)
    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】  回復(fù)  更多評(píng)論   

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

# re: PKU1925 Spiderman 【DP】  回復(fù)  更多評(píng)論   

2007-04-16 20:53 by oyjpart
謝謝提醒 呵呵
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲激情不卡| 欧美激情视频一区二区三区不卡| 欧美成人dvd在线视频| 欧美在线关看| 欧美新色视频| 在线视频日韩| av成人福利| 欧美精品入口| 亚洲欧洲三级| 亚洲福利视频网| 久久久久九九视频| 可以免费看不卡的av网站| 国产在线播精品第三| 亚洲欧美视频在线| 欧美一区二区三区在线免费观看| 国产精品久久久久三级| 洋洋av久久久久久久一区| 一区二区三区视频观看| 欧美日韩国产精品自在自线| 亚洲精品视频在线观看免费| 一区二区国产日产| 欧美午夜宅男影院在线观看| 正在播放欧美一区| 香蕉久久精品日日躁夜夜躁| 国产欧美日本一区二区三区| 欧美亚洲一区| 蜜臀a∨国产成人精品| 亚洲第一区中文99精品| 欧美顶级少妇做爰| 亚洲最新中文字幕| 午夜精品福利一区二区蜜股av| 国产精品国产一区二区| 欧美一区二区女人| 欧美高清不卡在线| 中文亚洲欧美| 国产欧美日韩综合一区在线观看 | 久久久中精品2020中文| 美女91精品| 日韩一级不卡| 国产精品日韩一区二区| 久久精彩视频| 亚洲精品一二区| 欧美一区二区三区在线视频| 激情久久一区| 欧美日韩国产精品成人| 亚洲在线一区二区| 欧美1区2区3区| 亚洲午夜国产一区99re久久| 国产日韩一区| 欧美精品一区二区视频| 亚洲自拍电影| 亚洲高清视频在线观看| 午夜亚洲性色福利视频| 亚洲国产高清自拍| 国产精品久久久久久久久婷婷| 久久精品99国产精品日本| 亚洲精品1区2区| 久久久久久91香蕉国产| 亚洲欧洲在线看| 国产日韩精品久久| 欧美日韩国产成人在线| 久久av一区二区三区亚洲| 亚洲免费观看视频| 女仆av观看一区| 午夜精品在线看| 日韩视频在线观看国产| 国产专区欧美专区| 欧美三级在线播放| 美国成人直播| 欧美在线观看视频| 国产精品99久久久久久人| 欧美bbbxxxxx| 久久精品夜色噜噜亚洲a∨| 一区二区三区欧美成人| 91久久精品网| 伊人久久亚洲热| 国产欧美日韩视频| 欧美色区777第一页| 欧美成人午夜影院| 久久综合亚洲社区| 久久精品欧美| 欧美在线黄色| 亚洲欧美日韩国产另类专区| 亚洲美女av在线播放| 亚洲福利一区| 欧美高清在线播放| 免费日韩av| 乱中年女人伦av一区二区| 欧美在线黄色| 欧美在线电影| 久久成人一区| 久久久久国产精品厨房| 欧美一区二区三区免费在线看| 亚洲在线一区二区三区| 国产精品99久久不卡二区| 日韩一级网站| 中国女人久久久| av不卡在线观看| 在线亚洲欧美专区二区| 正在播放亚洲一区| 亚洲视频一区二区免费在线观看| 亚洲乱码久久| 一区二区冒白浆视频| 日韩一区二区高清| 一区二区三区成人 | 99在线精品观看| 9人人澡人人爽人人精品| 亚洲看片一区| 亚洲一区二区精品在线| 亚洲欧美另类中文字幕| 午夜天堂精品久久久久| 欧美在线看片a免费观看| 久久久久亚洲综合| 欧美jizz19hd性欧美| 欧美国产一区二区| 亚洲人精品午夜在线观看| 99亚洲一区二区| 日韩一级黄色片| 午夜激情综合网| 久久久精品久久久久| 欧美大片免费观看| 欧美性大战久久久久久久蜜臀| 国产欧美韩日| 亚洲国产精品va在线观看黑人| 亚洲精品影院在线观看| 亚洲一区在线直播| 久久久久九九九| 91久久久久久久久| 亚洲一区免费网站| 久久日韩粉嫩一区二区三区| 欧美另类99xxxxx| 国产欧美日韩一区二区三区在线| 黄色成人小视频| 一本色道久久88精品综合| 欧美一级片在线播放| 欧美成人免费全部| 亚洲桃色在线一区| 久久综合亚洲社区| 国产精品一区在线播放| 亚洲第一在线视频| 亚洲欧美日韩成人| 亚洲成人中文| 性欧美在线看片a免费观看| 免费观看成人www动漫视频| 国产精品久久国产精麻豆99网站| 在线视频成人| 亚洲欧美一区二区视频| 亚洲国产第一| 欧美一区二区啪啪| 国产精品成人久久久久| 在线观看欧美黄色| 午夜日韩激情| 亚洲精选一区二区| 久久深夜福利免费观看| 国产精品亚发布| 99精品国产一区二区青青牛奶| 久久一区二区三区国产精品| 一区二区三区日韩在线观看| 美女视频黄免费的久久| 国产日韩欧美成人| 亚洲一级在线| 亚洲日本中文字幕免费在线不卡| 久久人人97超碰精品888| 国产欧美精品在线| 亚洲尤物在线| 亚洲毛片在线免费观看| 美女露胸一区二区三区| 激情综合色综合久久| 午夜精品影院| 亚洲午夜视频在线| 欧美日韩亚洲一区二区三区在线观看 | 性伦欧美刺激片在线观看| 欧美视频在线看| 一区二区日本视频| 亚洲精品一品区二品区三品区| 噜噜噜91成人网| 永久域名在线精品| 葵司免费一区二区三区四区五区| 午夜精品久久久久久久白皮肤| 乱中年女人伦av一区二区| 日韩午夜av在线| 欧美一区免费视频| 久久成人精品视频| 中日韩美女免费视频网站在线观看| 日韩午夜剧场| 欧美日韩日日骚| 在线亚洲电影| 一本色道久久综合狠狠躁篇的优点 | 日韩视频在线播放| 亚洲高清av| 欧美国产视频在线观看| 日韩视频一区二区三区在线播放免费观看 | 亚洲欧美日韩另类| 亚洲免费视频在线观看| 国产喷白浆一区二区三区 | 欧美一区二区三区四区在线观看地址| 中文日韩电影网站| 国产日韩欧美视频| 久久夜色精品亚洲噜噜国产mv | 欧美精品一区二区精品网|