這幾天又把14年給做了，這是day1的第三題
飛揚的小鳥
Flappy Bird 是一款風靡一時的休閑手機遊戲。玩家需要不斷控制點選手機螢幕的頻率來調節小鳥的飛行高度，讓小鳥順利通過畫面右方的管道縫隙。如果小鳥一不小心撞到了水管或者掉在地上的話，便宣告失敗。
【noip】【dp】飛揚的小鳥 背包 滾動數組 為了簡化問題，我們對遊戲規則進行了簡化和改編：
遊戲界面是一個長為 n，高為 m 的二維平面，其中有k 個管道（忽略管道的寬度）。
小鳥始終在遊戲界面内移動。小鳥從遊戲界面最左邊 任意整數高度位置出發，到達遊戲界面最右邊時，遊戲完成。
小鳥每個機關時間沿橫坐标方向右移的距離為 1，豎直移動的距離由玩家控制。如果點選螢幕，小鳥就會上升一定高度 X，每個機關時間可以點選多次，效果疊加； 如果不點選螢幕，小鳥就會下降一定高度 Y。小鳥位于橫坐标方向不同位置時，上 升的高度 X 和下降的高度 Y 可能互不相同。
小鳥高度等于 0 或者小鳥碰到管道時，遊戲失敗。小鳥高度為 m 時，無法再上升。
現在，請你判斷是否可以完成遊戲。如果可以，輸出最少點選螢幕數；否則，輸出小鳥最多可以通過多少個管道縫隙。
輸入格式
第 1 行有 3 個整數 n，m，k，分别表示遊戲界面的長度，高度和水管的數量，每兩個 整數之間用一個空格隔開；
接下來的 n 行，每行 2 個用一個空格隔開的整數 X 和 Y，依次表示在橫坐标位置 0~n-1 上玩家點選螢幕後，小鳥在下一位置上升的高度 X，以及在這個位置上玩家不點選螢幕時， 小鳥在下一位置下降的高度 Y。
接下來 k 行，每行 3 個整數 P，L，H，每兩個整數之間用一個空格隔開。每行表示一個管道，其中 P 表示管道的橫坐标，L 表示此管道縫隙的下邊沿高度為 L，H 表示管道縫隙上邊沿的高度（輸入資料保證 P 各不相同，但不保證按照大小順序給出）。
輸出格式
共兩行。
第一行，包含一個整數，如果可以成功完成遊戲，則輸出 1，否則輸出 0。 第二行，包含一個整數，如果第一行為 1，則輸出成功完成遊戲需要最少點選螢幕數，否則，輸出小鳥最多可以通過多少個管道縫隙。
樣例輸入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
1
6
樣例輸入2
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
樣例輸出2
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。
提示
如下圖所示，藍色直線表示小鳥的飛行軌迹，紅色直線表示管道。
【noip】【dp】飛揚的小鳥 背包 滾動數組 來源
NOIP2014 提高組 Day1
圖檔來源vijos
這道題一拿到手無論從題目條件還是資料範圍來看都是dp，問題就是怎麼dp，怎麼不會逾時，怎麼考慮清楚各種情況。
一開始我以為f[1000][10000]要超，就沒敢用，就寫成了滾動數組，那麼我這裡就幹脆将滾動數組算了。
我們定義f[i]表示在目前這個橫坐标，縱坐标為i是的最小點選次數，如果在上一步不能到達i，那麼就将i初始化為0。
那麼怎麼算？
很多同學會直接想到再在兩重循環裡面再加一重，來表示這一步跳幾下，這樣的話最壞時間複雜度就變成了O（nm*m/x)
根據測試，如果寫成這樣會T五個點，那麼我們就必須要優化，這是我們想到了以前學習的完全背包，是的，這裡可以用完全背包的思想優化
将這個想象成一個完全背包問題，一共有兩個物品，一個是點選螢幕一次，一個是向下墜，點選螢幕這個物品有無限個，而向下墜隻有1個，并且他們兩個不能同時去，但也不能一個不取。
這是我們的狀态轉移方程實際上是很簡單的，但我們還要考慮很多種情況。
狀态轉移方程：f[i]=min(f[i],f[i+y[i]],f[i-x[i]]+1)
但是不存在的情況不能算，而且如果他向上飛會撞牆，把這些情況都考慮了就可以了，dp不難，基本上都能想到。
代碼放下面，寫的有點複雜，可以用作參考。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 10005
#define N 1005
using namespace std;
int x[M],y[M],p[M],l[M],h[M],vis[N],g[M],d[N];
//vis表示是否這個點可以走到，d表示這個點是否需要臨時數組來更新
//g[i]表示前i個有多少水管，p[i]表示在i這個位置有沒有水管，對應的位置是什麼
int n,m,k;
int f[N],ff[N],ans;
//f是我們dp的主要數組，ff是臨時數組
int main()
{
#ifdef LOCAL
freopen("bird.in","r",stdin);
freopen("bird.out","w",stdout);
#endif
cin>>n>>m>>k;
for(int i=;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
for(int i=;i<=k;i++)
{
int a;
scanf("%d%d%d",&a,&l[i],&h[i]);
p[a]=i;
}
for(int i=;i<=n;i++)//初始化g
{
g[i]=g[i-];
if(p[i])g[i]++;
}
//memset(f,-63,sizeof(f));
for(int i=;i<=n;i++)
{
ans=;
memset(vis,,sizeof(vis));
memset(ff,,sizeof(ff));
memset(d,,sizeof(d));
bool bo=false;
for(int j=;j<=m;j++)//先判斷向下墜的情況，再放進臨時數組
{
if(f[j]<)continue;
int down=j-y[i];
if(down>&&(!p[i]||(p[i]&&down>l[p[i]]&&down<h[p[i]])))//判斷是否有柱子
{
ff[down]=f[j];
d[down]=;//更改标志，為後面更新做準備
}
}
for(int j=;j<=m;j++)//在考慮向上飛的情況
{
if(f[j]<)continue;
int up=j+x[i];
if(up>=m)up=m;//判斷碰頂
if(f[up]<||f[j]+<f[up])f[up]=f[j]+;//完全背包思想，重複向上更新
if(!p[i]||(p[i]&&up>l[p[i]]&&up<h[p[i]]))//判斷是否能飛到i點
{
if(f[up]<||f[j]+<=f[up])//思想同上，向上更新
{
f[up]=f[j]+;
vis[up]=;
continue;
}
if(d[up])ff[up]=min(ff[up],f[j]+);//如果無法向上更新存進臨時數組
else ff[up]=f[j]+; //因為有可能一會無法到達i點
d[up]=;
}
}
for(int j=;j<=m;j++)//将臨時數組與f合并，更新f
if(d[j])
{
if(!vis[j])f[j]=ff[j];
else f[j]=min(ff[j],f[j]);
vis[j]=;
}
for(int j=;j<=m;j++)//判斷是否可以繼續向前飛
{
if(!vis[j])f[j]=-;
else
{
bo=true;
ans=min(ans,f[j]);//求出最小步數（本來應該放在循環外，那樣要多些一個循環，我懶就寫裡面了）
}
}
if(!bo)//是否需要彈出0
{
cout<<<<'\n'<<g[i-];
return ;
}
}
cout<<<<'\n'<<ans;
}
如果有什麼問題，或錯誤，請在評論區提出，謝謝。