P1159岳麓山上打水
dfsID，第一次听说这东西，但是感觉不太靠谱啊。
一开始的时候，想到了排个序后，然后进行dp，如果要输出字典序最小其实还是可以搞定的，就是2、3、比26小的话，还是可以的。
排序后，只要在转移的时候，如果这个背包有解了的话，就不转移就行了。
但是这题坑爹在需要个数最小，这就不是字典序了。
那么暴力枚举选了多少个桶，那么有2^n种选法。每一种都dp一次。
但是据说，据说在很少步之内就能算出解，然后210ms过了。
26
2
2 26
27
3
2 7 27
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
bool dp[maxn];
int a[maxn];
int sel[maxn];
int tot, n;
int ans[maxn];
bool dfsID(int cur, int has, int up) {
if (has == up) {
for (int i = ; i <= tot; ++i) dp[i] = false;
dp[] = true;
for (int i = ; i <= has; ++i) {
for (int j = ans[i]; j <= tot; ++j) {
dp[j] = dp[j] || dp[j - ans[i]];
}
}
if (dp[tot]) {
cout << has << " ";
for (int i = ; i <= has; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
return dp[tot];
}
if (cur > n) return false;
if (n - cur + + has < up) return false;
ans[has + ] = a[cur];
return dfsID(cur + , has + , up) || dfsID(cur + , has, up);
}
void work() {
cin >> tot >> n;
assert(tot > );
for (int i = ; i <= n; ++i) {
cin >> a[i];
assert(a[i] > );
}
sort(a + , a + + n);
for (int i = ; i <= n; ++i) {
if (dfsID(, , i)) {
return;
}
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
work();
return ;
}