文章目錄

• T1：Star Way To Heaven
• • 題目
  • 題解
  • 代碼實現
• T2：飛揚的小鳥
• • 題目
  • 題解
  • 代碼實現

T1：Star Way To Heaven

題目

小 w 傷心的走上了 Star way to heaven。
到天堂的道路是一個笛卡爾坐標系上一個 n*m 的長方形通道 頂點在 (0,0) 和 (n,m) 。
小 w 從最左邊任意一點進入，從右邊任意一點走到天堂，最左最右的距離為 n，上下邊界距離為m 。
其中長方形有 k 個Star ，每個 Star 都有一個整點坐標，Star 的大小可以忽略不計。
每個 Star 以及長方形上下兩個邊緣宇宙的邊界都有引力，所以為了成功到達 heaven 小 w 離他們越遠越好。
請問小 w 走到終點的路徑上，距離所有星星以及邊界的最小距離最大值可以為多少？

輸入格式
一行三個整數n,m,k。
接下來 k 行，每行兩個整數 表示一個點的坐標。
輸出格式
一行一個數表示答案。保留到小數點后9位。

樣例
樣例輸入
10 5 2
1 1
2 3
樣例輸出
1.118033989
數據范圍與提示
對于 100% 的數據：k ≤ 6000；n,m ≤10⁶

題解

以考慮二分答案result，對k個star都建一個半徑為r的圓入手，
那么對于兩個相交的圓把它們弄到一個集合，
對上下邊界特殊判斷，如果說上下邊界被弄到了一個集合，
即說明，有若干個圓將矩形攔腰折斷，分成了兩個不連通的部分，是無法走到天堂的
則這個答案不合法，舍去

難道真的去搞二分？？
把幾個圓弄到一個集合就會想到并查集，再到kruskal，最后聯想到得到prim算法，
現將一個邊界加入集合，找到距離它最小的點，加入集合，
將與之相連的點的距離更新

如此加邊，知道另一邊界也加入集合中，此時剛好上下界攔腰截斷，其實這時的maxdis為恰好不能走過去時的最小dis，那么只要小一點點，就符合了，精度不用怕

代碼實現

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXN 6005 #define LL long long #define INF 10000000 int n, m, k; double result; double x[MAXN], y[MAXN], dis[MAXN]; bool vis[MAXN];double count ( int u, int v ) {return sqrt ( ( x[u] - x[v] ) * ( x[u] - x[v] ) + ( y[u] - y[v] ) * ( y[u] - y[v] ) ); }int main() {scanf ( "%d %d %d", &n, &m, &k );for ( int i = 1;i <= k;i ++ )scanf ( "%lf %lf", &x[i], &y[i] );for ( int i = 1;i <= k;i ++ )dis[i] = y[i];dis[k + 1] = m;for ( int i = 1;i <= k + 1;i ++ ) {int t = -1;double now = INF;for ( int j = 1;j <= k + 1;j ++ ) {if ( ! vis[j] && dis[j] < now ) {now = dis[j];t = j;}}result = max ( dis[t], result );if ( t == k + 1 ) return ! printf ( "%.9f", result * 0.5 );vis[t] = 1;for ( int j = 1;j <= k;j ++ ) {double tmp = count ( j, t );if ( ! vis[j] )dis[j] = min ( dis[j], max ( dis[t], tmp ) );}dis[k + 1] = min ( dis[k + 1], m - y[t] );}return 0; }

T2：飛揚的小鳥

題目

Flappy Bird是一款風靡一時的休閑手機游戲。玩家需要不斷控制點擊手機屏幕的頻率來調節小鳥的飛行高度，讓小鳥順利通過畫面右方的管道縫隙。如果小鳥一不小心撞到了水管或者掉在地上的話，便宣告失敗。

為了簡化問題，我們對游戲規則進行了簡化和改編:
游戲界面是一個長為 n，高為 m 的二維平面，其中有 k 個管道（忽略管道的寬度）。
小鳥始終在游戲界面內移動。小鳥從游戲界面最左邊任意整數高度位置出發，到達游戲界面最右邊時，游戲完成。

小鳥每個單位時間沿橫坐標方向右移的距離為 1，豎直移動的距離由玩家控制。如果點擊屏幕，小鳥就會上升一定高度 X，每個單位時間可以點擊多次，效果疊加；如果不點擊屏幕，小鳥就會下降一定高度 Y。小鳥位于橫坐標方向不同位置時，上升的高度 XX 和下降的高度 Y 可能互不相同。
小鳥高度等于 0 或者小鳥碰到管道時，游戲失敗。小鳥高度為 m 時，無法再上升。

現在,請你判斷是否可以完成游戲。如果可以，輸出最少點擊屏幕數；否則，輸出小鳥最多可以通過多少個管道縫隙。

輸入格式
第 1 行有 3 個整數 n, m, k分別表示游戲界面的長度，高度和水管的數量，每兩個整數之間用一個空格隔開；
接下來的 n 行，每行 22 個用一個空格隔開的整數 X 和 Y，依次表示在橫坐標位置 0～n?1 上玩家點擊屏幕后，小鳥在下一位置上升的高度 X，以及在這個位置上玩家不點擊屏幕時，小鳥在下一位置下降的高度 Y。
接下來 k 行，每行 33 個整數 P, L, H，每兩個整數之間用一個空格隔開。每行表示一個管道，其中 P 表示管道的橫坐標，L 表示此管道縫隙的下邊沿高度，H 表示管道縫隙上邊沿的高度（輸入數據保證 P 各不相同，但不保證按照大小順序給出）。

輸出格式
共兩行。
第一行，包含一個整數，如果可以成功完成游戲，則輸出 1，否則輸出 0。
第二行，包含一個整數，如果第一行為 1，則輸出成功完成游戲需要最少點擊屏幕數，否則，輸出小鳥最多可以通過多少個管道縫隙。

輸入輸出樣例
輸入
10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3
輸出
1
6

輸入
10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10
輸出
0
3
說明/提示
【輸入輸出樣例說明】
如下圖所示，藍色直線表示小鳥的飛行軌跡，紅色直線表示管道。

【數據范圍】
對于 30%的數據：5≤n≤10,5≤m≤10,k=0，保證存在一組最優解使得同一單位時間最多點擊屏幕 3次；
對于 50%的數據：5≤n≤20,5≤m≤10，保證存在一組最優解使得同一單位時間最多點擊屏幕 3 次；
對于 70%的數據：5≤n≤1000,5≤m≤100；
對于 100%的數據：5≤n≤10000, 5≤m≤1000，0≤k<n, 0 < X < m, 0 < Y < m, 0 < P < n， 0≤L<H≤m, L + 1 < H

題解

考慮$DP[i][j]$：表示當鳥在$(i,j)$時點擊屏幕的最少次數
1.鳥是從i-1掉下來的
$$DP[i][j]=DP[i?1][j+y[i]](j+y[i]\le m)$$
2.鳥是前面i-1多次點擊上來的
$$DP[i][j]=DP[i?1][j?x[i]?k](j\ge x[i]?k)$$
此時思考時間復雜度$O(nmk)$，肯定TLE
那么就可以將這種情況想成前面跳一次，然后自己往上豎直跳k-1次
$$DP[i][j]=min(DP[i?1][j?x[i]]+1,DP[i][j?x[i]]+1)$$
3.注意當往上跳過m的時候，鳥就一直在m處往后飛
4.因為x可能會有限制水管，所以算完后把水管賦值成INF，就可以了

---

其實這道題就是一個很板的背包問題，加一點點優化就可以了

代碼實現

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXM 2005 #define MAXN 10005 #define INF 0x3f3f3f3f int n, m, k; bool flag[MAXN]; int x[MAXN], y[MAXN]; int low[MAXN], high[MAXN]; int dp[MAXN][MAXM];int main() {scanf ( "%d %d %d", &n, &m, &k );for ( int i = 1;i <= n;i ++ )scanf ( "%d %d", &x[i], &y[i] );for ( int i = 1;i <= k;i ++ ) {int P, H, L;scanf ( "%d %d %d", &P, &L, &H );flag[P] = 1;low[P] = L;high[P] = H;}memset ( dp, 0x3f, sizeof ( dp ) );for ( int i = 1;i <= m;i ++ )dp[0][i] = 0;for ( int i = 1;i <= n;i ++ ) {for ( int j = x[i] + 1;j <= m + x[i];j ++ )dp[i][j] = min ( dp[i - 1][j - x[i]] + 1, dp[i][j - x[i]] + 1 );for ( int j = m;j <= m + x[i];j ++ )dp[i][m] = min ( dp[i][m], dp[i][j] );for ( int j = 1;j + y[i] <= m;j ++ )dp[i][j] = min ( dp[i][j], dp[i - 1][j + y[i]] );if ( flag[i] ) {for ( int j = 1;j <= low[i];j ++ )dp[i][j] = INF;for ( int j = high[i];j <= m;j ++ )dp[i][j] = INF;}}int result = INF;for ( int i = 1;i <= m;i ++ )result = min ( result, dp[n][i] );if ( result < INF )printf ( "1\n%d", result );else {int i, j, tot = 0;for ( i = n;i >= 1;i -- ) {for ( j = 1;j <= m;j ++ )if ( dp[i][j] < INF )break;if ( j <= m )break;}for ( int j = 1;j <= i;j ++ )if ( flag[j] )tot ++;printf ( "0\n%d", tot );}return 0; }

總結

以上是生活随笔為你收集整理的Star Way To Heaven （prim最小生成树） // [ NOIP提高组 2014]飞扬的小鸟（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

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