dfs,x的范围似乎不是100而是1000
View Code //zoj1711#include#include #include #include using namespace std;const int maxnum = 1001, maxn = 12;int t, n, sum[maxnum], number[maxn][2], answer[maxn], total;bool found;void init(){ int i, x; memset(sum, 0, sizeof(sum)); memset(answer, 0, sizeof(answer)); found = false; total = 0; for (i = 0; i < n; i++) { cin >> x; sum[x]++; } for (i = 1000; i >= 1; i--) if (sum[i] > 0) { number[total][0] = i; number[total][1] = sum[i]; total++; }}void print(){ int i, j; bool first = true; if (!found) { found = true; cout << "Sums of " << t << ":\n"; } for (i = 0; i < n; i++) for (j = 1; j <= answer[i]; j++) if (first) { cout << number[i][0]; first = false; } else { cout << "+" << number[i][0]; } cout << endl;}void make(int temp, int space){ int i; if (space == 0) { print(); return; } if (temp == total) return; for (i = number[temp][1]; i >= 0; i--) if (space - i * number[temp][0] >= 0) { answer[temp] = i; make(temp + 1, space - i * number[temp][0]); } answer[temp] = 0;}int main(){ //freopen("t.txt", "r", stdin); while (cin >> t >> n, n | t) { init(); make(0, t); if (!found) { cout << "Sums of " << t << ":\n"; cout << "NONE\n"; } } return 0;}