USACO milk4 枚舉答案再檢驗

　　剛開始寫了一個暴力的dfs超時了， 最后看了下題解說是先枚舉答案再判斷，然后就寫了雙dfs，全部秒殺，代碼如下：

/*ID: m1500293LANG: C++PROG: milk4
*/
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
int Q, P;
int t[110];bool dfs1(int dept, int a[], int num, int rQ)
{if(rQ==0) return true;if(dept==num) return false;bool res = false;for(int i=1; i<=Q/a[dept]; i++){if(rQ-a[dept]*i >= 0)res = res || dfs1(dept+1, a, num, rQ-a[dept]*i);}return res;
}
bool flog;
void dfs(int dept, int a[], int num, int nn)
{if(flog) return ;if(num > nn) return;if(num == nn){if(dfs1(0, a, num, Q)){printf("%d ", num);for(int i=0; i<num; i++)printf("%d%c", a[i], i==num-1?'\n':' ');flog = true;}return ;}if(dept == P) return;a[num] = t[dept];dfs(dept+1, a, num+1, nn);dfs(dept+1, a, num, nn);
}
bool cmp(const int &a, const int &b)
{return a<b;
}
int main()
{freopen("milk4.in", "r", stdin);freopen("milk4.out", "w", stdout);scanf("%d%d", &Q, &P);for(int i=0; i<P; i++) scanf("%d", &t[i]);sort(t, t+P, cmp);int a[110];flog = false;for(int i=1; i<=P&&!flog; i++){dfs(0, a, 0, i);}return 0;
}

?