论如何把一个完全背包出的高大上……

这个题啊……细节特别多……

首先，不建议开滚动数组，细节处理就会疯。

然后呢……真的不太好说了……还是看代码吧（尽管代码还是有明显的滚动数组痕迹）。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)

int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
    int n,m,k,temp;
    register int i,j,v,now,pre,ans=INF,cnt;
    scanf("%d%d%d",&n,&m,&k);
    cnt=k;
    REP(i,n){
        scanf("%d%d",&A[i][0],&A[i][1]);
    }
    for(i=0;i<=n;i++){
        GZ[i][0]=0;
        GZ[i][1]=m+1;
    }
    REP_B(i,k){
        scanf("%d",&temp);
        haveGZ[temp]=true;
        scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
    }
    memset(d,0x7f,sizeof(d));
    memset(d[0],0,sizeof(d[0]));
    d[0][0]=INF;
    REP_B(i,n){
        now=i;
        pre=i-1;
        d[now][0]=INF;
        int& X=A[i-1][0];
        int& Y=A[i-1][1];
        REP_B(j,m){
            if(j-X>0 && d[pre][j-X]<INF)
                d[now][j]=min(d[now][j],d[pre][j-X]+1);
            if(j-X>0 && d[now][j-X]<INF)
                d[now][j]=min(d[now][j],d[now][j-X]+1);
            if(j==m)
                for(v=j-X;v<=m;v++){
                    if(d[pre][v]<INF)
                        d[now][j]=min(d[now][j],d[pre][v]+1);
                    if(d[now][v]<INF)
                        d[now][j]=min(d[now][j],d[now][v]+1);
                }
        }
        for(j=GZ[i][0]+1;j<GZ[i][1];j++){
            if(j+Y<=m && d[pre][j+Y]<INF)
                d[now][j]=min(d[now][j],d[pre][j+Y]);
        }
        if(haveGZ[i]){
            REP_B(j,GZ[i][0])
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
            for(j=GZ[i][1];j<=m;j++)
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
        }
    }
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            ans=min(ans,d[i][j]);
        }
        if(ans<INF)
            break;
        if(haveGZ[i])
            cnt--;
    }
    if(cnt==k){
        printf("1\n%d\n",ans);
    }else{
        printf("0\n%d\n",cnt);
    }
    return 0;
}

• 相关文章
• 全局相关文章