2017 Multi-University Training Contest - Team 5-Rikka with Subset

​​题目传送门​​

题目大意：

有一个数列 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[],反过来求。

#include<cstdio>
#include<cstring>
#include<algorithm>
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;
}