题目描述

Flappy Bird是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 nn ，高为 mm 的二维平面，其中有 kk 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 11 ，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 XX ，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 YY 。小鸟位于横坐标方向不同位置时，上升的高度 XX 和下降的高度 YY 可能互不相同。

小鸟高度等于 00 或者小鸟碰到管道时，游戏失败。小鸟高度为 mm 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

Solution

这道题是一道类似于01背包与完全背包混合加上一些特判的题。

看到数据范围，完全就是为O（nm）而设计的，所以我们放心的设计下状态，dp【i】【j】表示小鸟到ij点时最少的点击次数。

这道题细节很多，接下来一点一点说。

因为要求最小值，所以初始值全是INF，dp【0】【1~m】=0，表示小鸟可以从这个范围开始飞行。

考虑小鸟可以怎么飞。

点一次屏幕，小鸟上升x高度，但可以点多次，所以可以从i状和i-1状态转移；

不点屏幕，小鸟下落，但只能下落一次，所以直接从i-1转移即可（PS一定要在上升状态转移完之后再去考虑这种转移，否则bird会有升有降的）

转移从1-m（否则会少很多种情况），再把小鸟达不到的范围设置成INF即可（这样就很完美了）。

我们在dp时可以设置一个标记flag，当可行范围内的点被更新过后就打标记，如果一次dp后没有标记说明不可行，直接break。

#include
     
      #include
      
       using namespace std;int dp[10009][1009],n,m,k,kk,vis[10009];struct de{int x,y;}a[10009];struct sd{int x,low,up;}b[10009];int main(){scanf("%d%d%d",&n,&m,&k);for(int i=0;i
       
        =1)dp[i][j]=min(min(dp[i][j],dp[i][j-a[i-1].x]+1),dp[i-1][j-a[i-1].x]+1);if(j==m)for(int l=m;l>=m-a[i-1].x;--l)dp[i][j]=min(min(dp[i][j],dp[i-1][l]+1),dp[i][l]+1);if(j<=up&&j>=low&&dp[i][j]!=0x3f3f3f3f)flag=0;}for(int j=1;j<=m;++j){if(j+a[i-1].y<=m)dp[i][j]=min(dp[i][j],dp[i-1][j+a[i-1].y]); if(j<=up&&j>=low&&dp[i][j]!=0x3f3f3f3f)flag=0;}for(int j=0;j<=low-1;++j)dp[i][j]=0x3f3f3f3f;for(int j=up+1;j<=m;++j)dp[i][j]=0x3f3f3f3f;if(flag){cout<<0<
        
         <