POJ 1925 Spiderman(DP)

题意： Spiderman从最左边的楼通过将蛛丝粘到后边的某座楼顶，然后荡过去，接着发射蛛丝荡过去，直到到达最后的楼。问最少发射几次蛛丝。

思路：从横坐标 j 能跳过建筑物 i 需满足： (p[i].x - j)*(p[i].x - j) <= p[i].y*p[i].y - (p[i].y - p[0].y)*(p[i].y-p[0].y). 从横坐标 j 经建筑物 i 后到达横坐标 2 * p[i].x - j。

所以状态转移方程是： dp[2 * p[i] .x- j] = min(dp[2 * p[i].x - j] , d[j] + 1)。因为这个人走的是圆弧，每荡一次所达到的终点一定是与最开始的那座楼的高度等高。

先遍历楼，然后遍历位置，第二层循环找他要荡到哪儿，因为是对称的。

 1 //1925
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <iostream>
 6 
 7 using namespace std ;
 8 
 9 struct node
10 {
11     long long x ;
12     long long  y ;
13 }p[5120] ;
14 int dp[2051532] ;
15 
16 int main()
17 {
18     int K ,N;
19     scanf("%d",&K) ;
20     while(K--)
21     {
22         scanf("%d",&N) ;
23         for(int i = 0 ; i < N ; i++)
24             scanf("%I64d %I64d",&p[i].x,&p[i].y) ;
25         memset(dp,100,sizeof(dp)) ;
26         dp[p[0].x] = 0 ;
27         for(int i = 1 ; i < N ; i++)
28             for(int j = p[i].x-1 ; j >= p[0].x ; j--)
29         {
30             long long  dis = (p[i].x-j)*(p[i].x-j)+(p[i].y-p[0].y)*(p[i].y-p[0].y) ;
31             if(dis > (long long)(p[i].y*p[i].y))
32                 break ;
33             dp[2*p[i].x-j] = min(dp[2*p[i].x-j],dp[j]+1) ;
34         }
35         int ans = 99999999 ;
36         for(int i = p[N-1].x ; i <= 2*p[N-1].x ; i++)
37             ans = min(ans,dp[i]) ;
38         if(ans >= 99999999)
39             ans = -1 ;
40         printf("%d
",ans) ;
41     }
42     return 0 ;
43 }

View Code