洛谷 P1941 飞扬的小鸟【dp】

设f[i][j]为在坐标(i,j)时的最小点击次数，转移的话从i-1向上飞或者向下掉转移，注意转移完了之后要把管子部分赋值为inf

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10005,inf=1e9;
int n,m,k,p,ans,a[N],b[N],x[N],y[N],f[N][1005];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    a[n]=m+1;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]),a[i]=m+1;
    for(int i=1;i<=k;i++)
        scanf("%d",&p),scanf("%d%d",&b[p],&a[p]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            f[i][j]=inf;
    f[0][0]=inf;
    for(int i=1;i<=n;i++)
    {
        for(int j=x[i];j<=m;j++)
            f[i][j]=min(f[i][j],min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1));
        for(int j=m-x[i];j<=m;j++)
            f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));
        for(int j=b[i]+1;j<=a[i]-1;j++)
            if(j+y[i]<=m)
                f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
        for(int j=1;j<=b[i];j++)
            f[i][j]=inf;
        for(int j=a[i];j<=m;j++)
            f[i][j]=inf;
    }
    ans=inf;
    int cnt=k;
    for(int i=n;i>=1;i--)
    {
        for(int j=b[i]+1;j<=a[i]-1;j++)
            ans=min(ans,f[i][j]);
        if(ans!=inf)
            break;
        if(a[i]!=m+1)
            cnt--;
    }
    if(cnt==k)
        printf("1\n%d\n",ans);
    else
        printf("0\n%d\n",cnt);

    return 0;
}

洛谷 P1941 飞扬的小鸟【dp】

原文：https://www.cnblogs.com/lokiii/p/9614363.html