CSP-S 2022 第一轮 第42题：完善程序（第 20 题）第 4 空

题目

(2)（容器分水） 有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：

1. FILL(i)：用水龙头将容器 $i(i \in {1,2})$ 灌满水；
2. DROP(i)：将容器 i 的水倒进下水道；
3. POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。

求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。

试补全程序。

#include <bits/stdc++.h>
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 << "FILL(1)" << endl;
        go(a, y);
    } else if (f[x][y] == dfs(x, b) + 1) {
        cout << "FILL(2)" << endl;
        go(x, b);
    } else if (f[x][y] == dfs(0, y) + 1) {
        cout << "DROP(1)" << endl;
        go (0, y);
    } else if (f[x][y] == dfs(x, 0) + 1) {
        cout << "DROP(2)" << endl;
        go(x, 0);
    } else {
        int t = min(a - x, y);
        if(f[x][y] == ④) {
            cout << "POUR(2,1)" << endl;
            go(x + t, y - t);
        } else {
            t = min(x, b - y);
            if (f[x][y] == ⑤) {
                cout << "POUR(1,2)" << endl;
                go(x - t, y + t);
            } else
                assert(0);
        }
    }
}

int main() {
    cin >> 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);
    }
}

④处应填（ ）

选项

• A. dfs(x + t, y - t) + 1
• B. dfs(x + t, y - t) - 1
• C. dfs(x - t, y + t) + 1
• D. dfs(x - t, y + t) - 1

答案

A

题解

选 A：dfs(x + t, y - t) + 1。

这一分支输出的是 POUR(2,1)，即把容器 2 的水倒入容器 1。

倒水量为： ``cpp int t = min(a - x, y); ` 其中 a - x 是容器 1 的剩余容量，y 是容器 2 的现有水量，所以倒水后的状态是 (x + t, y - t)`。

程序通过下面的条件判断这一步是否在最优操作序列上：

> 当前状态的最少操作数 = 倒水后状态的最少操作数 + 本次倒水的 1 次操作。

因此④应填： ``cpp dfs(x + t, y - t) + 1 ``