http://poj.org/problem?id=1925

題意：

蜘蛛俠的女朋友被壞人抓到了?tower (目標點)，他必須盡快從?apartment（起點）到tower去救人，給出n個建筑物的坐標以及高度（第一個為起點最后一個為目標點），求蜘蛛俠用蜘蛛網最少蕩幾次才能到達tower？注意：這里在起點之后的建筑物保證高度都會大于等于起點的高度。

思路：

首先計算每個點i的來源點j的取值范圍，然后枚舉這個范圍，遞歸的求解。假設來源點為j 則有x[i] - sqrt(h[i]*h[i] - (h[i] - H)*(h[i] - H)) <= j < x[i]; 其中x[i]為i建筑物的坐標，h[i]為i建筑物高度，H為h[0]，注意這里在蜘蛛俠的每個停留點他的高度必為h[0]（對稱性）枚舉來源點后計算有j可能到達的點pos = 2*(x[i] - j) + j = 2*x[i] - j;即可：

PS：注意再用sqrt()求解釋h[i]*h[i]會超數據類型，所以我使用了double型，你也可以直接用三角函數求解這樣就不用考慮超數據類型的了。

View Code #include <cstdio> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define CL(a,num) memset(a,num,sizeof(a)) #define maxn 5007 #define N 1000004 using namespace std;const int inf = 1999999;int dp[N]; int x[maxn]; double h[maxn]; int n;int main() {//freopen("din.txt","r",stdin);int i,j,t;scanf("%d",&t);while (t--){scanf("%d",&n);for (i = 0; i < n; ++i)scanf("%d%lf",&x[i],&h[i]);CL(dp,-1);dp[x[0]] = 0;double H = h[0];int ans = inf;for (i = 1; i < n; ++i)//枚舉每個建筑物 {double tmp = sqrt((h[i]*h[i]*1.0 - 1.0*(h[i] - H)*(h[i] - H))*1.0);int l = x[i] - (int)tmp;//計算可能的來源點for (j = max(x[0],l); j < x[i]; ++j)//枚舉來源點 {if (dp[j] != -1){if (2*x[i] - j >= x[n -1])//2*x[i] - j就是可能到達的點 {ans = min(ans,dp[j] + 1);}else if (dp[2*x[i] - j] == -1 || dp[2*x[i] - j] > dp[j] + 1)dp[2*x[i] - j] = dp[j] + 1;}}}if (ans != inf) printf("%d\n",ans);else printf("-1\n");}return 0; }

?

?

轉載于:https://www.cnblogs.com/E-star/archive/2012/08/13/2636351.html

總結

以上是生活随笔為你收集整理的pku 1925 Spiderman DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。