首页 > 代码库 > hdu 6092 Rikka with Subset(01背包)
hdu 6092 Rikka with Subset(01背包)
题目链接:hdu 6092 Rikka with Subset
题意:
给你n和m,让你找一个字典序最小的含有n个数的A序列,使得A序列的和为m,
然后给你m+1个数,是A序列所有的集合的和的个数,然后让你找出这个A序列。
题解:
和题解一样的思想。
1 #include<bits/stdc++.h> 2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 typedef long long ll; 6 typedef pair<int,int>P; 7 8 const int N=1e4+7; 9 int t,n,m,ed,an[N],cnt; 10 P ans[N]; 11 ll b[N],dp[N]; 12 13 int main(){ 14 scanf("%d",&t); 15 while(t--) 16 { 17 scanf("%d%d",&n,&m); 18 mst(dp,0);dp[0]=1;ed=0; 19 F(i,0,m)scanf("%lld",b+i); 20 F(i,1,m) 21 { 22 if(dp[i]<b[i]) 23 { 24 ans[++ed]=P(i,b[i]-dp[i]); 25 int en=b[i]-dp[i]; 26 F(j,1,en)for(int k=m;k>=i;k--) 27 dp[k]+=dp[k-i]; 28 } 29 } 30 cnt=0; 31 F(i,1,ed) 32 { 33 while(ans[i].second--) 34 an[++cnt]=ans[i].first; 35 } 36 F(i,1,cnt)printf("%d%c",an[i]," \n"[i==cnt]); 37 } 38 return 0; 39 }
hdu 6092 Rikka with Subset(01背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。