题解：P2409 Y的积木

bingzhi314 · 2025-07-23 15:51:22 · 题解

题目

经过多次尝试后，发现用堆是做不出来了。

于是还是用了背包。

由题可见，本题用分组

于是可写以下代码：

for(int i=1;i<=n;i++){  
      for(int j=0;j<=m;j++){//注：
            for(int k=1;k<=v[i][0];k++){
                if(v[i][k]<=j){
                    f[i][j]+=f[i-1][j-v[i][k]];
                }
            }
       }
}

虽不允许不选第i组的物品，但j很小时可能会存在某些组的物品一个也放不进的情况，但是这不影响我们要求的答案。因为，题目描述的前x小的体积和，在遍历到他们（某个j）时，每个组肯定肯定存在物品v[i]<j，而每个组都能选出一个物品，因此不存在某个组选不出物品的情况 。这是可推的。 但交上去，却惊奇的发现《100pts》。

这个出现是因为有时候long long数组溢出变负

故：

for(int i=1;i<=n;i++){  
      for(int j=0;j<=m;j++){//注：
            for(int k=1;k<=v[i][0];k++){
                if(v[i][k]<=j){
                    f[i][j]+=f[i-1][j-v[i][k]];
                    if(f[i][j]>c){
                          f[i][j]=c;
                    }
                }
            }
        }
    }

大于k的减去。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,x,c,m; 
int v[110][110];
long long f[110][10010];
int main(){
    f[0][0]=1;
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i][0]);
        int ma=-0x3f3f3f3f;
        for(int j=1;j<=v[i][0];j++){
            scanf("%d",&v[i][j]);
            ma=max(ma,v[i][j]);
        }
        m+=ma;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=1;k<=v[i][0];k++){
                if(v[i][k]<=j){
                    f[i][j]+=f[i-1][j-v[i][k]];
                    if(f[i][j]>c){
                          f[i][j]=c;
                    }
                }
            }
        }
    }
    int cnt=0;
    for(int j=1;j<=m;j++){
        if(f[n][j]>0){
            int t=f[n][j];
            while(t>0&&cnt<c){
                cnt++;
                printf("%d ",j);
                t--;
            }
        }
    }
    puts("");//记得换行，自求多福吧。。
    return 0; 
}