本文共 1629 字，大约阅读时间需要 5 分钟。

题目大意：

有一个数列 a[] ,长度n（n<=50），其实就是题目要你输出的数列。b[i] 表示元素和为 i 的集合个数（不明白看下面的样例解释）。给你一个数列 b[] ，长度m（m<=10000），让你求 a[]，并按照其字典序最小输出。

样例解释：

1. a[]={1,2} 数列a的子数列有{}，{1}，{2}，{1,2}，正好2^n个，所以有b[]为{1,1,1,1}，为什么呢？{}代表0吧，只有一次是吧，{1}，{2}，{1,2}也是一样的意思，代表1,2,3，也都是一次，所以b[]={1,1,1,1}
2. a[]={1,1,1} 数列a的子数列有{},{1},{1},{1},{1,1},{1,1},{1,1},{1,1,1},也是正好2^n个，不就是0,1,1,1,2,2,2,3，所以b[]={1,3,3,1}吧，应该明白了吧。

所以现在就是给你b[]要你求 a[],反过来求。

思路：

首先我们用dp[k]代表当1～k-1中的数字确定后（就是1~k-1中的数字已经选择完了，当然是把数字选到a[]啊），凑到和为k的个数，就是要使用1~k-1的数凑到和为k,如{1，1}是2，就是这个意思，不够就表示，需要单独使用k这个数字来凑，就是当b[2]=4的时候，因为求2之前已经求了1，当dp[1]=3，即{1}，{1}，{1}，所以只有{1,1}，{1,1}，{1,1}(只是一个例子，不要纠结是不是符合题目意思)，所以是不是要选择一个{2}了，每次选择一个数是不是会有蝴蝶效应呢？当然啦，当你选择了一个数字2后，假如原来有dp[1]=3,dp[2]=1，那么dp[3]是不是多了3个，因为在{1}插入{2}是不是就相当于{1,2}={3}了，所以dp[4]多了1个，所以有这样一种关系，当你选择了一个数K到a[]中， 就会有这样的关系： for(int i=m;i<=K;i–) dp[i]+=dp[i-k]; 为什么是从m-k呢？不能k-m吗？你自己画个图看看，如果从k-m，是不是有些已经加到结果里的数字会存在再加了一遍的情况，所以是从m-k,所以这样思路清楚了，该写代码啦。。。

AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int maxn=1e4+10;int A[100],B[maxn],dp[maxn];int main(){
   	int T,n,m;	scanf("%d",&T);	while(T--)	{
   		scanf("%d%d",&n,&m);		for(int i=0;i<=m;i++)		scanf("%d",&B[i]);		memset(dp,0,sizeof(dp));		dp[0]=1;//每个集合都有一个空子集		int tot=1;		for(int i=1;i<=m;i++)		{
   			int len=B[i]-dp[i];//这就是因为1～i-1中的数确定后，能凑到和为i的个数，不够的话，说明a序列中有B[i]-dp[i]个数的i			for(int j=1;j<=len;j++)			{
   				A[tot++]=i;//前面确定的数，无法达到要求，还要加入B[i]-dp[i]个i				for(int k=m;k>=i;k--)				{
   					dp[k]+=dp[k-i];//反着来，避免已经加到结果里的数字再加一遍，这里有01背包的感觉,并且每次加入i都要更新一次dp[]				}			}		}		for(int i=1;i<=n;i++)//根据题目意思显然n==tot-1,所以不管是n还是tot-1都可以		printf("%d%c",A[i],i==n?'\n':' ');//输出	}	return 0;}
     
    
   

转载地址：https://kaven.blog.csdn.net/article/details/77100176 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！