題目網(wǎng)址：

https://vjudge.net/problem/HDU-6092

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:?

Yuta has?nn?positive?A1?AnA1?An?and their sum is?mm. Then for each subset?SS?of?AA, Yuta calculates the sum of?SS.?

Now, Yuta has got?2n2n?numbers between?[0,m][0,m]. For each?i∈[0,m]i∈[0,m], he counts the number of?iis he got as?BiBi.?

Yuta shows Rikka the array?BiBi?and he wants Rikka to restore?A1?AnA1?An.?

It is too difficult for Rikka. Can you help her???

Input

The first line contains a number?t(1≤t≤70)t(1≤t≤70), the number of the testcases.?

For each testcase, the first line contains two numbers?n,m(1≤n≤50,1≤m≤104)n,m(1≤n≤50,1≤m≤104).

The second line contains?m+1m+1?numbers?B0?Bm(0≤Bi≤2n)B0?Bm(0≤Bi≤2n).

Output

For each testcase, print a single line with?nn?numbers?A1?AnA1?An.?

It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.

Sample Input

2 2 3 1 1 1 1 3 3 1 3 3 1

Sample Output

1 2 1 1 1

Hint

In the first sample, $A$ is $[1,2]$. $A$ has four subsets $[],[1],[2],[1,2]$ and the sums of each subset are $0,1,2,3$. So $B=[1,1,1,1]$

解題思路：

用dp[j]來表示組成 j 所需的方案數(shù)，那么對(duì)于數(shù) i 來說，數(shù) i 的個(gè)數(shù)就是子序列中和為 i 的個(gè)數(shù)即 b[i] 減去其他數(shù)字組成 i 的個(gè)數(shù)即 dp[i]，由此可以算出數(shù)字 i 的個(gè)數(shù)。

由于dp[j]來表示組成 j 所需的方案數(shù)，那么對(duì)于dp[j]來說，dp[j] = dp[j] + dp[j-i]

因此我們可以先遍歷要確定的數(shù)字即最外層的循環(huán) for(ll i=1;i<=m;i++)，再確定數(shù)字 i 的個(gè)數(shù)，內(nèi)兩層循環(huán)相當(dāng)于一個(gè)01背包，以確定更新dp數(shù)組

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; ll a[120]; ll dp[10100]; ll b[10020]; int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;scanf("%d",&t);while(t--) {ms(dp);int n,m;scanf("%d %d",&n,&m);rep(i,0,m) scanf("%I64d",&b[i]);dp[0]=1;int cnt=0;for(ll i=1;i<=m;i++) {if(b[i]) {if(cnt==n) break;ll num=b[i]-dp[i];for(ll j=1;j<=num;j++) {a[++cnt]=i;for(ll k=m;k>=i;k--) {dp[k]=dp[k]+dp[k-i];}}}}for(int i=1;i<cnt;i++) {printf("%I64d ",a[i]);}printf("%I64d\n",a[cnt]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU6092——Rikka with Subset 【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。