完善程序（2） 第6-10题，组合题 （容器分水）有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为： 1）FILL(i)：用水龙头将容器 i（i∈{1,2}）灌满水； 2）DROP(i)：将容器 i 的水倒进下水道； 3）POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。 求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。 试补全程序。 #include using namespace std; const int N = 110; int f[N][N]; int ans; int a, b, c; int init; int dfs(int x, int y) { if (f[x][y] != init) return f[x][y]; if (x == c || y == c) return f[x][y] = 0; f[x][y] = init - 1; f[x][y] = min(f[x][y], dfs(a, y) + 1); f[x][y] = min(f[x][y], dfs(x, b) + 1); f[x][y] = min(f[x][y], dfs(0, y) + 1); f[x][y] = min(f[x][y], dfs(x, 0) + 1); int t = min(a - x, y); f[x][y] = min(f[x][y], ① ); t = min(x, b - y); f[x][y] = min(f[x][y], ② ); return f[x][y]; } void go(int x, int y) { if ( ③ ) return; if (f[x][y] == dfs(a, y) + 1) { cout > a >> b >> c; ans = 1 << 30; memset(f, 127, sizeof f); init = **f; if ((ans = dfs(0, 0)) == init - 1) cout << "impossible"; else { cout << ans << endl; go(0, 0); } }
正确答案：完善程序①答案D。POUR(2,1)，①处应填 dfs(x + t, y - t) + 1。
试卷来源：2022 CSP-S提高级（第一轮）C++真题