题目大意
有a, b, c三个牛奶桶, 每个牛奶桶的容量是1到20的整数。一开始a,b为空, c为满,可以互相倒,问当a桶为空时,c桶中的奶的体积有几种情况?
样例输入&输出
sample input 1
8 9 10
sample output 1
1 2 8 9 10
sample input 2
2 5 10
sample output 2
5 6 7 8 9 10
分析&反思
继续帮助回忆dfs的一题。
1. 推导状态, 判断状态, 回溯。
2. 类比bfs, 当局面相同时,去重, 有点哈希的感觉。
3. 输出答案的时候忘记了0,是一个非常容易忘记的点。
代码
#include#include #include #include using namespace std; int a, b, c, atop, btop, ctop; int ans[22], vis[22][22]; void dfs(int x, int y) { if(vis[x][y]) return; vis[x][y] = 1; if(!x) ans[ctop - b]++; int cha, dao; { cha = btop - b; dao = min(a, cha); a -= dao; b += dao; dfs(a, b); a += dao; b -= dao; } { cha = atop - a; dao = min(b, cha); b -= dao; a += dao; dfs(a, b); b += dao; a -= dao; } { cha = ctop - c; dao = min(a, cha); a -= dao; c += dao; dfs(a, b); a += dao; c -= dao; } { cha = atop - a; dao = min(c, cha); c -= dao; a += dao; dfs(a, b); c += dao; a -= dao; } { cha = btop - b; dao = min(c, cha); c -= dao; b += dao; dfs(a, b); c += dao; b -= dao; } { cha = ctop - c; dao = min(b, cha); b -= dao; c += dao; dfs(a, b); b += dao; c -= dao; } return ; } int anss[30], tot; int main() { freopen("milk3.in", "r", stdin); freopen("milk3.out", "w", stdout); cin >> atop >> btop >> ctop; c = ctop; dfs(a, b); for(int i = 0; i <= 20; i++) if(ans[i]) anss[++tot] = i; for(int i = 1; i < tot; i++) cout << anss[i] << " "; cout << anss[tot] << endl; return 0; }