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;
}