题解 P1941 【飞扬的小鸟 】

这题有可能和愤怒的小鸟是cp？？反正都是dp。。

恩，这题是一道背包。就是说小鸟在往上飞的时候是完全背包，然后往下掉的时候是01背包。

为了不冲突，就是先做完全，然后再做01，最后将不合法的剔除。

最后输出最后一列的最小值，如果全是INF那么就输出0。【这个是错的】

我也不知道为什么【可能数据有错？？】，但是只要是过了最后一根水管，就算是完成【因为这个WA了n次】。

但好像题面上说是要到最后一列才算完成，希望管理员能看一看这个问题？？

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXDP=100000;
int l[10010],h[10010];
int dp[10010][1010];
int x[10010],y[10010];
bool p[10010];
int main()
{
    int n,i,j,k,m,w;
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        l[i]=0;
        h[i]=m+1;
    }
    l[n]=0;
    h[n]=m+1;
    for(i=0;i<k;i++)
    {
        scanf("%d",&w);
        scanf("%d%d",&l[w],&h[w]);
        p[w]=true;
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            dp[i][j]=MAXDP;
        }
    }
    dp[0][0]=MAXDP;
    for(i=1;i<=m;i++)
    {
        dp[0][i]=0;
    }
    for(i=1;i<=n;i++)
    {
        for(j=x[i-1];j<=m;j++)
        {
            if(j==m)
            {
                for(w=m-x[i-1];w<=m;w++)
                {
                    dp[i][j]=min(dp[i][j],dp[i-1][w]+1);
                    dp[i][j]=min(dp[i][j],dp[i][w]+1);
                }
            }
            dp[i][j]=min(dp[i][j],dp[i-1][j-x[i-1]]+1);
            dp[i][j]=min(dp[i][j],dp[i][j-x[i-1]]+1);
        }
        for(j=max(1,l[i]+1);j<=min(m-y[i-1],h[i]-1);j++)
        {
            dp[i][j]=min(dp[i][j],dp[i-1][j+y[i-1]]);
        }
        for(j=l[i];j>=1;j--)
        {
            dp[i][j]=MAXDP;
        }
        for(j=h[i];j<=m;j++)
        {
            dp[i][j]=MAXDP;
        }
    }
    int ans=MAXDP;
    int cnt=k;
    for(i=n;i>=1;i--)
    {
        for(j=l[i]+1;j<=h[i]-1;j++)
        {
            ans=min(ans,dp[i][j]);
        }
        if(ans<MAXDP)
        {
            break;
        }
        if(p[i]==true)
        {
            k--;
        }    
    }
    if(cnt==k)
    {
        printf("1\n%d",ans);
    }
    else
    {
        printf("0\n%d",k);
    }
    return 0;
}