【题目】

CSP-S 2022 提高级 第一轮 完善程序（2）
(2)（容器分水） 有两个容器，容器1的容量为为a升，容器2的容量为b升；同时允许下列的三种操作，分别为：
FILL(i)：用水龙头将容器 i(i \in {1,2})i(i∈1,2) 灌满水；
DROP(i)：将容器 i 的水倒进下水道；
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);
    }
}

①～⑤处应填（ ）
1.
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
2.
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
3.
A. x == c || y == c
B. x == c && y == c
C. x >= c || y >= c
D. x >= c && y >= c
4.
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
5.
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

【题目考点】

1. 动态规划
2. 记忆化递归

【解题思路】

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、b、c，分别表示：容器1的容量为为a升，容器2的容量为b升，最终某个容器中要得到c升水。
ans初值设为 2 30 2^{30} 230
127作为1字节的值，2进制下为0111 1111。用16进制数表示为0x7f，每字节值为0x7f，memset使int类型数组f的每个元素的值都设为0x7f7f7f7f，在十进制下为2139062143（不需要知道这个数的具体数值，只需要知道这是个很大的数即可），可以将0x7f7f7f7f这个数认为是无穷大。
init=**f，**f就是f[0][0]的值，为0x7f7f7f7f。也就是将init设为无穷大。
而后调用dfs(0,0)。

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];
}

题目要求的是想得到c升水最少的操作数，输出的是ans，是dfs(0,0)的返回值f[0][0]。可以想到，dfs(x,y)求的是当前容器1有x升水、容器2有y升水，经过最少几次操作可以得到某容器有c升水。这是个记忆化递归的算法，f[x][y]为记忆化递归保存的状态，表示当前容器1有x升水、容器2有y升水，要想得到某容器有c升水的最少操作次数。

    if (f[x][y] != init)
        return f[x][y];

f[x][y]的初值为0x7f7f7f7f，也就是init。如果f[x][y]初值不为init，则该状态已经求出来了，不需要再进行递归求解。
如果f[x][y]初值为init，则需要求出f[x][y]。

    if (x == c || y == c)
        return f[x][y] = 0;

如果x或y为c，就是容器1中的水或容器2中的水是c升，那么已经得到了目标状态，该状态到目标状态需要操作的步骤是0步，所以设f[x][y]=0，返回结果。
f[x][y] = init - 1;
init-1表示从该状态出发无论经过几次任何操作都无法达到某容器有c升水的目标状态。如果接下来的过程中f[x][y]的值始终为init-1，那么容器1有x升水同时容器2有y升水，就无法通过容器倒水达到某容器有c升水的情况。
以下为在容器1有x升水容器2有y升水的情况下，经过1次操作后，使得容器1有M升水容器2有N升水（M、N表示某种可能的数值）
，从该情况出发不断倒水直至某容器有c升水的操作序列（该操作序列的步数通过dfs(M, N)求出），加上刚才的一次操作得到的操作序列，就是一个备选的从容器1有x升水容器2有y升水的情况下经过不断操作直到某容器有c升水的操作序列。如果该操作序列的步数比已知的最小步数f[x][y]更少，则更新最少步数f[x][y]。
f[x][y] = min(f[x][y], dfs(a, y) + 1);下一步的操作为将容器1中的水加满到a升。
f[x][y] = min(f[x][y], dfs(x, b) + 1);下一步的操作为将容器2中的水加满到b升。
f[x][y] = min(f[x][y], dfs(0, y) + 1);下一步的操作为将容器1中的水倒空。
f[x][y] = min(f[x][y], dfs(x, 0) + 1);下一步的操作为将容器2中的水倒空。

int t = min(a - x, y);
f[x][y] = min(f[x][y], ①);

容器1还剩下空间a-x，a-x和y的较小值t为从容器2倒水到容器1所倒的水的升数
倒水后，容器1增加t升变为x+t，容器2减少t升变为y-t，求出从该情况到某容器有c升水的步数为dfs(x+t, y-t)，再加1，就是一个备选的从容器1有x升水容器2有y升水的情况下经过不断操作直到某容器有c升水的操作步数。
因此空(1)填dfs(x+t, y-t)+1，选A。

t = min(x, b - y);
f[x][y] = min(f[x][y], ②);

容器2还剩下空间b-y，b-y和x的较小值t为从容器1倒水到容器2所倒的水的升数
倒水后，容器1减少t升变为x-t，容器2增加t升变为y+t，求出从该情况到某容器有c升水的步数为dfs(x-t, y+t)，再加1，就是一个备选的从容器1有x升水容器2有y升水的情况下经过不断操作直到某容器有c升水的操作步数。
因此空(2)填dfs(x-t, y+t)+1，选C。

主函数中，如果调用dfs(0,0)的返回值ans等于init-1，就输出“impossible”，否则输出ans，并调用go(0,0)。go函数的作用就是输出倒水的过程。

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);
        }
    }
}

go(x,y)的意义是：输出从容器1有x升水容器2有y升水，到某容器有c升水的操作序列。该函数是一个尾递归函数，一旦递归结束，那么整个函数调用过程就结束了。
因此第（3）空的位置应该填“整个操作序列结束”的条件，也就是某容器已经有c升水。也就是x == c || y == c，第（3）空选A。
以下如果f[x][y] ==dfs(M, N)+1，就说明从当前容器1有x升水容器2有y升水经过一次操作后使得容器1有M升水容器2有N升水，而后不断操作直到某容器有c升水的操作步数和从当前容器1有x升水容器2有y升水不断操作直到某容器有c升水的最少操作步数f[x][y]相同，那么该操作就是可行的，输出这一次的操作，然后再输出从容器1有M升水容器2有N升水，到某容器有c升水的操作序列。

	  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);
      }

t = min(a - x, y)是从容器2倒水到容器1的倒水升数。
如果这一步操作是从容器2倒水到容器1，而后从容器1有x+t升水容器2有y-t升水不断倒水直到某容器有c升水的最小操作步数dfs(x+t, y-t)+1就等于从容器1有x升水容器2有y升水不断操作直到某容器有c升水的最少操作步数f[x][y]，那么输出这一步操作，而后输出从容器1有x+t升水容器2有y-t升水，到某容器有c升水的操作序列。
所以第（4）空选A。
同理t = min(x, b - y)是从容器1倒水到容器2的倒水升数。
如果这一步操作是从容器1倒水到容器2，而后从容器1有x-t升水容器2有y+t升水不断倒水直到某容器有c升水的最小操作步数dfs(x-t, y+t)+1就等于从容器1有x升水容器2有y升水不断操作直到某容器有c升水的最少操作步数f[x][y]，那么输出这一步操作，而后输出从容器1有x-t升水容器2有y+t升水，到某容器有c升水的操作序列。
所以第（5）空选C。

【答案】

  1. A
  2. C
  3. A
  4. A
  5. C
# 算法
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

cover

人工智能在库存管理中的应用

avatar 开放原子开发者工作坊

dubbo启动报错failed to bind nettyserver on

dubbo报错今天启动项目的时候，关掉了custom服务，<dubbo:consumer check="false"/>并且关掉了spring的elastic-job，<!--<import resource="cloud-elastic-job.xml"/>-->但是还是报错，看了下错误代码，原因是因...

avatar 开放原子开发者工作坊
cover

【Windows】redis安装

avatar 开放原子开发者工作坊