飞扬的小鸟

题意

今天的题意很难简化诶，就提醒一下吧，就算没有管道（障碍物），也是有上下界的哦。

分析

我们令表示为在第列，第行所需要的最小点击次数。那如果是上升，状态转移方程就类似完全背包转移方式；如果是下降状态转移方程就类似背包转移方式。飞行过程中如果高度超过了那就需要特判来降为。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e3+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m,k;
int f[N][N];
bool e[N];
struct node
{
    int x,y;
}fly[N];
struct node1
{
    int up,down;
}map_[N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int main()
{
    n=read();m=read();k=read();
    for(int i=1;i<=n;i++)    fly[i].x=read(),fly[i].y=read();    
    for(int i=1;i<=n;i++) 
        map_[i].up=m,map_[i].down=1;
    for(int i=1;i<=k;i++) 
    {
        int a;a=read();
        e[a]=1;
        map_[a].down=read()+1;
        map_[a].up=read()-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=fly[i].x+1;j<=m+fly[i].x;j++)
            f[i][j]=min(f[i-1][j-fly[i].x]+1,f[i][j-fly[i].x]+1);
        for(int j=m+1;j<=m+fly[i].x;j++)
            f[i][m]=min(f[i][m],f[i][j]);
        for(int j=1;j<=m-fly[i].y;j++)
            f[i][j]=min(f[i][j],f[i-1][j+fly[i].y]);
        for(int j=1; j<map_[i].down;j++)
            f[i][j]=f[0][0];
        for(int j=map_[i].up+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;
}