首页 > 代码库 > 【洛谷P2409】Y的积木
【洛谷P2409】Y的积木
这是一道dp……
f [ i ] [ j ] 表示前 i 组,总和为 j 时的方案数
f [ i ] [ j + a [ i ] [ k ] ] <-- f [ i - 1 ] [ j ]
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=105,M=11000; 6 int f[N][M],a[N][N],maxl[N],maxn,n,Q; 7 int main(){ 8 maxn=0; 9 scanf("%d %d",&n,&Q); 10 for (int i=1;i<=n;i++){ 11 scanf("%d",&a[i][0]); 12 for (int j=1;j<=a[i][0];j++){ 13 scanf("%d",&a[i][j]); 14 if (a[i][j]>maxl[i]) 15 maxl[i]=a[i][j]; 16 } 17 maxn+=maxl[i]; 18 sort(a[i]+1,a[i]+a[i][0]+1); 19 } 20 for (int i=1;i<=a[1][0];i++) 21 f[1][a[1][i]]++;//初始化不能赋成1 22 for (int i=2;i<=n;i++) 23 for (int j=1;j<=maxn;j++){ 24 if (!f[i-1][j]) 25 continue; 26 for (int k=1;k<=a[i][0];k++) 27 f[i][j+a[i][k]]+=f[i-1][j]; 28 } 29 int p=1,j=0; 30 while (p<=Q){ 31 j++; 32 for (int i=1;i<=f[n][j];i++){ 33 if (p>Q) return 0; 34 printf("%d ",j); 35 p++; 36 } 37 } 38 return 0; 39 }
【洛谷P2409】Y的积木
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。