首页 > 代码库 > POJ 1925 Spiderman(DP)

POJ 1925 Spiderman(DP)

2024-07-14 07:13:59   216人阅读

题目链接

题意 ： 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 node10 {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\n",ans) ;41     }42     return 0 ;43 }
View Code

 


联系
我们