题库 信息学奥赛题库 题目列表 (容器分水) 有两个容器,容器 1 的容...
组合题

(容器分水) 有两个容器,容器 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 <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);
              }
       }
}

第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

题目信息
完善程序 2022年 初赛
-
正确率
0
评论
277
点击