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背包转移方式

细节题,注意细节

#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;
}