首页 > 代码库 > 洛谷P2409 Y的积木
洛谷P2409 Y的积木
题目背景
Y是个大建筑师，他总能用最简单的积木拼出最有创意的造型。
题目描述
Y手上有n盒积木，每个积木有个重量。现在他想从每盒积木中拿一块积木，放在一起，这一堆积木的重量为每块积木的重量和。现在他想知道重量和最小的k种取法的重量分别是多少。（只要任意更换一块积木，就视为一种不同的取法。如果多种取法重量总和一样，我们需要输出多次。）
输入输出格式
输入格式：第一行输入两个整数，n,k，意义如题目所描述。
每组数据接下来的n行，第一个整数为mi，表示第i盒积木的数量，在同一行有mi个整数，分别表示每个积木的重量。
输出格式：一行，重量最小的k种取法的重量，要求对于每个数据，从小到大输出
输入输出样例
输入样例#1：
3 104 1 3 4 53 1 7 94 1 2 3 5
输出样例#1：
3 4 5 5 6 6 7 7 7 7
说明
对于30%的数据：2<=mi<=10,1<=n<=10
对于50%的数据：2<=mi<=50,1<=n<=50
对于100%的数据：2<=mi<=100,1<=n<=100,1<=k<=10000,每个积木的重量为不超过100的正整数，所有mi的积大于等于k。本题不卡常。
总和不超过10000，分组背包DP，看数值x可以被组合出几次，然后从小到大输出k个可以被组合出的次数即可
1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 const int mxn=101;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 int n,k;17 int m[mxn];18 int a[mxn][mxn];19 int f[mxn][mxn*mxn];20 int smm[mxn];21 int main(){22 n=read();k=read();23 int i,j;24 int mx=0;25 for(i=1;i<=n;++i){26 mx=0;27 m[i]=read();28 for(j=1;j<=m[i];++j){29 a[i][j]=read();30 if(a[i][j]>mx)mx=a[i][j];31 }32 sort(a[i]+1,a[i]+m[i]+1);33 smm[i]=smm[i-1]+mx;34 }35 f[0][0]=1;36 for(i=1;i<=n;++i){37 for(j=smm[i];j;--j){38 for(int l=1;l<=m[i];++l){39 if(a[i][l]>j)break;40 f[i][j]+=f[i-1][j-a[i][l]];41 }42 }43 }44 for(i=1;i<=smm[n];++i){45 while(f[n][i] && k){46 --f[n][i];--k;47 printf("%d ",i);48 }49 }50 return 0;51 }
洛谷P2409 Y的积木
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。