題目大意：

給出n個建筑，每個建筑以兩個數x，y表示，x代表它在橫軸上的位置，y代表這個建筑的高度。所有建筑的高度都大于等于第一個建筑的高度。所有建筑輸入順序按照x，y從小到達的順序排列。

蜘蛛俠在第一個建筑上，他要去最后一個建筑救女朋友。一直他每一次搖擺都會到關于建筑對稱的位置。求到最后一個建筑的最小搖擺次數。

解題思路：一開始以為很容易，dp[i]表示到達第i個建筑的最小搖擺次數，dp[i] = max(dp[k]+1),結果WA。。看了別人的思路才明白，這道題我想的太簡單了。WA原因：未能解決后效性問題，假設有k和j，都滿足dp[j] + 1 == dp[k] + 1,但兩個位置擺動的幅度不同，對之后的狀態會有影響。

所以這道題正解是dp[i]表示在x軸的i位置時的最小擺動次數。狀態方程不變。

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;const int maxn = 5005; struct Node {__int64 x,y; }building[maxn]; int n,dp[1000005];int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%I64d%I64d",&building[i].x,&building[i].y);memset(dp,-1,sizeof(dp));dp[building[1].x] = 0;for(int i = 2; i <= n; i++){int dis = sqrt(building[i].y * building[i].y - (building[i].y - building[1].y) * (building[i].y - building[1].y) + 0.5);for(int j = 1; j <= dis; j++) //dis表示離建筑i最遠的距離。{if(building[i].x - j < building[1].x) break;if(dp[building[i].x - j] == -1) continue;int tmp = min(building[i].x + j,building[n].x);if(dp[tmp] == -1) dp[tmp] = dp[building[i].x - j] + 1;else dp[tmp] = min(dp[tmp],dp[building[i].x - j] + 1);}}printf("%d\n",dp[building[n].x]);}return 0; }

總結

以上是生活随笔為你收集整理的poj 1925(坐标上的dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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