P1941 [NOIP2014 提高组] 飞扬的小鸟 题解(至少一个物品的完全背包)

题目链接

题目思路

点屏幕当成至少一个物品的完全背包来做：

一个物品(f[i][j] = min(f[i][j], f[i-1][j – x[i]] + 1);)

大于等于1个物品(f[i][j] = min(f[i][j], f[i][j – x[i]] + 1);)

然后下降当作01背包

细节比较多

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m,k;
int dp[maxn][2000+5];
int x[maxn],y[maxn];
int low[maxn],high[maxn];
int pre[maxn];
bool vis[maxn];
signed main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
        low[i]=0;
        high[i]=m+1;
    }
    for(int i=1,a,b,c;i<=k;i++){
        scanf("%d%d%d",&a,&b,&c);
        vis[a]=1;
        low[a]=b;
        high[a]=c;
    }
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+vis[i];
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=m;i++){
        dp[0][i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=x[i];j<=m+x[i];j++){
            dp[i][j]=min(dp[i-1][j-x[i]]+1,dp[i][j-x[i]]+1);
        }
        for(int j=m+1;j<=m+x[i];j++){
            dp[i][m]=min(dp[i][m],dp[i][j]);
            dp[i][j]=inf;
        }
        for(int j=1;j<=m-y[i];j++){
            dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]);
        }
        for(int j=0;j<=low[i];j++){
            dp[i][j]=inf;
        }
        for(int j=high[i];j<=m;j++){
            dp[i][j]=inf;
        }
    }
    int ans=inf;
    for(int i=1;i<=m;i++){
       ans=min(ans,dp[n][i]);
    }
    if(ans<inf){
        printf("1
%d
",ans);
    }else{
        printf("0
");
        for(int i=n-1;i>=1;i--){
            for(int j=1;j<=m;j++){
                if(dp[i][j]<inf){
                    printf("%d
",pre[i]);
                    i=0;
                    break;
                }
            }
        }
    }
    return 0;
}