洛谷-1941 飛揚的小鳥

題目描述

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

為了簡化問題，我們對遊戲規則進行了簡化和改編:

遊戲界面是一個長為 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 表示此管道縫隙的下邊沿高度，H 表示管道縫隙上邊沿的高度（輸入資料保證 PP 各不相同，但不保證按照大小順序給出）。

輸出格式：

共兩行。

第一行，包含一個整數，如果可以成功完成遊戲，則輸出 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

說明

【資料範圍】

對于 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

解釋：動态規劃，f[i][j]為坐标為i,高度為j的最小值，上升是完全背包，下降是01背包，直接套模闆就好了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10000+10;
const int maxm=2000+10;
int n,m,p;
int x[maxn],y[maxn];   
int low[maxn],high[maxn];   
int f[maxn][maxm];   
bool e[maxn];
int main() {
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1; i<=n; ++i) scanf("%d%d",&x[i],&y[i]);
    for(int i=1; i<=n; ++i) {
        low[i]=1;
        high[i]=m;
    }
    int a,b,c;
    for(int i=1; i<=p; ++i) {
        scanf("%d%d%d",&a,&b,&c);
        e[a]=1;
        low[a]=b+1;
        high[a]=c-1;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1; i<=m; ++i) f[0][i]=0;
    for(int i=1; i<=n; ++i) {
        for(int j=x[i]+1; j<=m+x[i]; ++j)
            f[i][j]=min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1);
        for(int j=m+1; j<=m+x[i]; ++j)
            f[i][m]=min(f[i][m],f[i][j]);
        for(int j=1; j<=m-y[i]; ++j)
            f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
        for(int j=1; j<low[i]; ++j)
            f[i][j]=f[0][0];
        for(int j=high[i]+1; j<=m; ++j)
            f[i][j]=f[0][0]; 
    }
    int ans=f[0][0];
    for(int j=1;j<=m;++j){
        ans=min(ans,f[n][j]);
    }
    if(ans<f[0][0]) printf("1\n%d\n",ans);
    else{
        int i,j;
        for(i=n;i>=1;i--) {
            for(j=1;j<=m;++j) {
                if(f[i][j]<f[0][0]) break;
            }
            if(j<=m) break;
        }
        ans=0;
        for(int j=1;j<=i;++j) {
            if(e[j]) ans++;
        }
        printf("0\n%d\n",ans);
    }
    return 0;
}