HDU6092Rikka with Subset(逆向背包)

题意：

有一个数列 a[] ,长度（n<=50）。b[i] 表示元素和为 i 的集合个数。给你一个数列 b[] ，长度（m<=10000），让你求 a[]，并按照其字典序最小输出

题解：

如果 B_iB?i?? 是 $B$ 数组中除了 B_0B?0?? 以外第一个值不为 $0$ 的位置，那么显然 $i$ 就是 $A$ 中的最小数。

现在需要求出删掉 $i$ 后的 $B$ 数组，过程大概是反向的背包，即从小到大让 B_j-=B_{j-i}B?j???=B?j?i??。

时间复杂度 $O(nm)$。

PS：理解一下之后其实就是一个逆向的多重背包

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
typedef long long ll;
const int maxn = 10105;
ll b[maxn];
int ans[55];
int main()
{int t, n, m;scanf("%d", &t);while(t--){scanf("%d%d", &n, &m);for(int i =  0; i <= m; i++)scanf("%I64d", &b[i]);int cnt = 0;for(int i = 1; i <= m; i++){if(b[i] == 0) continue;if(cnt == n) break;ans[cnt++] = i;for(int j = i; j <= m; j++)b[j] -= b[j-i];i--;}for(int i = 0; i < n; i++)printf("%d%c", ans[i], i == n-1 ? '\n' : ' ');}return 0;
}

容易理解点的代码：

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
typedef long long ll;
const int maxn = 10105;
ll b[maxn], dp[maxn];
int ans[55];
int main()
{int t, n, m;scanf("%d", &t);while(t--){scanf("%d%d", &n, &m);for(int i =  0; i <= m; i++)scanf("%I64d", &b[i]), dp[i] = 0;dp[0] = 1;int cnt = 0;for(int i = 1; i <= m; i++){int num = b[i] - dp[i];if(cnt == n) break;for(int j = 0; j < num; j++){ans[cnt++] = i;for(int k = m; k >= i; k--)dp[k] += dp[k-i];}}for(int i = 0; i < n; i++)printf("%d%c", ans[i], i == n-1 ? '\n' : ' ');}return 0;
}