P1941 飞扬的小鸟 题解

想当年我也是过了17个柱子的人呢hhh

---

题意很明显，相信各位都接触过这个游戏并且理解题意。

考虑到游戏界面有上下界m的问题，我们可以把m看做背包容量进行背包；

对于单个横坐标的连续点击上升，很明显是完全背包；对于不点就下降，很明显是点击或者不点击，01背包。跑2个背包即可。

对于卡上界m的情况，需要全部枚举出来并和上界的情况取min，因为小鸟一旦到上界就上不去了。

一个差不多类似于背吧模板+应用题的题目

code：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 10005
using namespace std;
int read()
{
    int ans=0;
    char ch=getchar(),last=' ';
    while(ch>'9'||ch<'0')last=ch,ch=getchar();
    while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
    return last=='-'?-ans:ans;
}
int n,m,k,p,l,h,judge[N],low[N],hi[N],f[N][2007];
int ans;
struct zbx{
    int a,b;
}zb[N];
int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)
    {
        zb[i].a=read(),zb[i].b=read();    
    }
    for(int i=1;i<=n;i++)
    {
        hi[i]=m;low[i]=1;
    }
    for(int i=1;i<=k;i++)
    {
        p=read(),low[p]=read()+1,hi[p]=read()-1;
        judge[p]=1;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=m;i++)
    {
        f[0][i]=0;//renyigaodu
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=zb[i].a+1;j<=m+zb[i].a;j++)
        {
            f[i][j]=min(f[i-1][j-zb[i].a],f[i][j-zb[i].a])+1;
        }
        for(int j=m+1;j<=m+zb[i].a;j++)
        {
            f[i][m]=min(f[i][j],f[i][m]);
        }
        for(int j=1;j<=m-zb[i].b;j++)
        {
            f[i][j]=min(f[i-1][j+zb[i].b],f[i][j]);
        }
        for(int j=1;j<=m;j++)
        {
            if(j<low[i]||j>hi[i])
            {
                f[i][j]=f[0][0];
            }
        }
    }
    ans=f[0][0];
    for(int j=1;j<=m;j++)
    {
        ans=min(f[n][j],ans);
    }
    if(ans<f[0][0])
    {
        printf("1
%d
",ans);
    }
    else
    {
        int i=n,j;
        for(;i>=1;i--)
        {
            for(j=1;j<=m;j++)
            {
                if(f[i][j]<f[0][0])break;
            }
            if(j<m+1)break;
        }
        ans=0;
        for(int kkk=1;kkk<=i;kkk++)
        {
            if(judge[kkk])//判断kkk是否为坏人
            ans++; 
        }
        printf("0
%d
",ans);
    }
    return 0;
}

noip rp++；