飞扬的小鸟

飞扬的小鸟

分析

1. 直接进入正题

2. 单取一个位置来看，假设当前为第 i 列，高度为 j ，这个高度要么是从位置 i - 1 落下来，要么则是点击屏幕飞上来的，这难道不是一个状态转移方程？即枚举当前位置和高度，设为f [ i ] [ j ]，则

   

   但是注意，这个空间是有限的——高度不可能低于1或高于m，所以得单独列出考虑。

   scanf("%d%d%d",&n,&m,&k);//输入
   for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),bird[i].l=0,bird[i].h=m+1;
   //每一个位置的可行移动位置以及点击与未点击变换的高度
   for (int i=1;i<=k;i++)
   {
      int x;
      scanf("%d",&x);
      flag[x]=1;
      scanf("%d%d",&bird[x].l,&bird[x].h);
   }//输入管道
   
   memset(f[0],0,sizeof(f[0]));
   
   for (int i=1;i<=n;i++)
   {
      int op=m+a[i];
      for (int j=a[i]+1;j<=op;j++) f[i][j]=min(f[i-1][j-a[i]],f[i][j-a[i]])+1;
   //假设当时没有m的限制
      for (int j=m+1;j<=op;j++) f[i][m]=min(f[i][m],f[i][j]);
   //重新更新此时到达高度m的最小步数
      for (int j=m-b[i];j>=1;j--) f[i][j]=min(f[i][j],f[i-1][j+b[i]]);
   //不点击屏幕
      for (int j=1;j<=bird[i].l;j++) f[i][j]=INF;
      for (int j=bird[i].h;j<=m;j++) f[i][j]=INF;
   //把限制区域的状态设为不合法即可
   }

3. 考虑和发育不合法的情况。合法就不用说了，如果不合法，那么肯定是在某一次管道就没了(QwQ,这游戏还能这样)。那么后续状态都无法得到转移。那么我们直接找到最后一次的合法状态，然后找到他们之间有多少管道即可。

代码

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

const int N=1e4+3,M=2e3+2;

int n,m,k;
int a[N],b[N];
int f[N][M];

bool flag[N];

struct Bird
{
    int p,l,h;
}bird[N];

int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),bird[i].l=0,bird[i].h=m+1;
    for (int i=1;i<=k;i++)
    {
        int x;
        scanf("%d",&x);
        flag[x]=1;
        scanf("%d%d",&bird[x].l,&bird[x].h);
    }

    memset(f[0],0,sizeof(f[0]));

    for (int i=1;i<=n;i++)
    {
        int op=m+a[i];
        for (int j=a[i]+1;j<=op;j++) f[i][j]=min(f[i-1][j-a[i]],f[i][j-a[i]])+1;
        for (int j=m+1;j<=op;j++) f[i][m]=min(f[i][m],f[i][j]);
        for (int j=m-b[i];j>=1;j--) f[i][j]=min(f[i][j],f[i-1][j+b[i]]);

        for (int j=1;j<=bird[i].l;j++) f[i][j]=INF;
        for (int j=bird[i].h;j<=m;j++) f[i][j]=INF;
    }

    int res=INF;
    for (int i=1;i<=m;i++) res=min(f[n][i],res);

    if(res>1e9)
    {
        printf("0\n");

        int i;
        for(i=n;i>=1;i--)
        {
            bool flg=false;
            for (int j=m;j>=1;j--) if(f[i][j]<INF) flg=1;
            if(flg) break;
        }

        int ans=0;
        for (int k=1;k<=i;k++) if(flag[k]) ans++;

        printf("%d\n",ans);

        return 0;
    }

    printf("1\n%d",res);

    return 0;
}