全部知识点
(容器分水)有两个容器,容器 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);
}
}
}
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 升,容器 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);
}
}
}
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 升,容器 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);
}
}
}
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 升,容器 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);
}
}
}
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 升,容器 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);
}
}
}
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);
}
}⑤处应填( )。
C语言“教父”是?
世界上最好的编程语言是?
哪种星座的程序员最富有创造性?
程序员最喜欢的衣服是?
程序员的节日是多少号?
以下哪个人是真正的技术大佬?
一个程序员在游泳时溺水。他会拼命的呼救:
请看以下情景:
「老板:下班前代码一定要发到线上哈!
程序员:好的。」
请问,最终代码什么时候会上线?
程序员小A结婚,程序员B去参加婚礼,随份子钱时说,凑个整吧好记
请问呢,小B随了多少钱?
几个程序员去饭店吃饭,在饭店点餐,点了一份“鱼香肉丝”,结果讨论一番不要鱼香肉丝了,随即改了点餐单
请问最后饭店服务员上了多少份鱼香肉丝?
老婆让程序员老公去买菜,临出门时说:去买个西瓜回来,要是有西红柿就买两个
如果菜市场什么都有。
请问,程序员老公最后会买回来什么?
以下哪项不是程序员最不喜欢的事情?
下列对顺序存储的有序表(长度为 n)实现给定操作的算法中平均时间复杂度为O(1)的是()。
现有非空双向链表 L,其结点结构为
| jrer | Data | Next |
“s- > next=p-> next;p- > next=s”,后,还要执行()。prer是指向直接前驱结点的指针,next是指向直接后继结点的指针。若要在L中指针p所指向的结点(非尾结点)之后插入指针s指向的新结点,则在执行了语句序列:
若采用三元组表存储结构存储稀疏矩阵M。则除三元组外,下列数据中还需要保存的是( ) 。
I、M 的行数 II、M中包含非零元素的行数
III、M 的列数 IV、M 中包含非零元素的列数