题目链接：传送门
题目大意：
给你n个砝码a，从中去掉m个后求最多的砝码可表示的重量。
n≤20，m≤4，m＜n，a≤100。
思路：
用dfs搜掉m个砝码，然后用队列dp跑出答案，维护答案。
时间复杂度是O(C* na)。
#include <bits/stdc++.h> using namespace std; int N, M, sum;
int a[];
bool vis[];
bool f[]; int ans; void dp()
{
queue <int> Q;
Q.push();
for (int i = ; i < N; i++) if (!vis[i]) {
int len = Q.size();
while (len--) {
int cur = Q.front(); Q.pop();
int nxt = cur + a[i];
if (!f[nxt]) {
f[nxt] = true;
Q.push(nxt);
}
Q.push(cur);
}
}
int cnt = ;
for (int i = ; i <= sum; i++) {
if (f[i]) {
cnt++;
f[i] = false;
}
}
ans = max(cnt, ans);
} void dfs(int dep, int cur)
{
if (dep == M) {
dp();
}
for (int i = cur; i < N; i++) {
if (!vis[i]) {
vis[i] = true;
sum -= a[i];
dfs(dep+, i+);
sum += a[i];
vis[i] = false;
}
}
} void init()
{
cin >> N >> M;
sum = ;
ans = ;
memset(f, false, sizeof f);
memset(vis, false, sizeof vis);
for (int i = ; i < N; i++) {
scanf("%d", a+i);
sum += a[i];
}
sort(a, a+N);
} int main()
{
init();
dfs(, );
cout << ans << endl;
return ;
}