NOIP2014飞扬的小鸟
陈子骏
2018-10-16 16:46:29
题目大意
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。
为了简化问题,我们对游戏规则进行了简化和改编:
1. 游戏界面是一个长为n,高 为m的二维平面,其中有
k个管道(忽略管道的宽度)。
2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
3. 小鸟每个单位时间沿横坐标方向右移的距离为1,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度X,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度Y。小鸟位于横坐标方向不同位置时,上升的高度X和下降的高度Y可能互不相同。
4. 小鸟高度等于0或者小鸟碰到管道时,游 戏 失 败 。小 鸟 高 度 为m时,无法再上升。
5. 现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙
Solution
用f[i][j]表示横坐标为i时高度为j的最少点击次数。
用正无穷来表示不可能达到这个状态。
于是我们可以分析出状态转移的方式:
上升——完全背包转移方式
下降——01背包转移方式
细节题,注意细节
```cpp
#include<bits/stdc++.h>
using namespace std;
int f[10001][1001];
int x[10001],y[10001];
int b[10001],h[10001];
int vis[10001];
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++)scanf("%d%d",&x[i],&y[i]);
for(int i=0;i<=n;i++) {b[i]=0;h[i]=m+1;}
for(int i=1;i<=k;i++){
int x;
scanf("%d",&x);scanf("%d%d",&b[x],&h[x]);vis[x]=1;}
memset(f,999999,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;j++)
{
if(j==m)
for(int w=m-x[i-1];w<=m;w++)
{
f[i][j]=min(f[i][j],f[i-1][w]+1);
f[i][j]=min(f[i][j],f[i][w]+1);
}
f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1);
f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1);
}
for(int j=b[i]+1;j<=min(m-y[i-1],h[i]-1);j++)
f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);
for(int j=b[i];j>=1;j--)
f[i][j]=999999;
for(int j=h[i];j<=m;j++)
f[i][j]=999999;
}
int cnt=k;int ans=999999;
for(int i=n;i>=1;i--)
{
for(int j=b[i]+1;j<=h[i]-1;j++)
ans=min(ans,f[i][j]);
if(ans<999999)break;
if(vis[i]==1)k--;
}
if(cnt==k)
cout<<"1"<<endl<<ans;
else
cout<<"0"<<endl<<k;
return 0;
}
```