梦想星际舰队第7关 迷宫 && FCOI #6 第4题迷宫题解【原创】
本帖最后由 zhangjinxuan 于 2023-8-20 17:24 编辑梦想星际舰队第7关 && FCOI #6 题解
第四题：迷宫
题目描述
你带着一个 sumv 容积的背包来到了一个 a 行 b 列的迷宫，你可以向下或者向右移动，但不能出界或者碰到障碍。
迷宫中有 n 种宝藏，还有 m 个障碍。
第 i 种宝藏的位置是 x1 i 行 y1 i 列，每个的体积是 vi ，但为你带来的收益每个都是 w_i ，一共有 l_i 个，当你的位置有一种或一些宝藏，你可以拾取这种的零个或多个，每获取一个就会获得 wi 的收益，同时，每一个对应的宝藏会占用你背包 vi，若背包占用满了或无法放下时，它将无法放入，你也得不到这个收益。
当然，不同种类的宝藏的位置可能会重合。
第 i 个障碍的位置是 x2 i 行 y2 i 列，保证宝藏的位置不是障碍的位置。
现在给你这个迷宫的信息，即障碍、大小、宝藏的信息，请求出，如果要从 1 行 1 列出发，到迷宫上任意非障碍的一点，你获得的最大收益是多少？
输入格式
a b
n m sumv
x1_1 y1_1 v_1 w_1 l_1
x1_2 y1_2 v_2 w_2 l_2
...
x1_n y1_n v_n w_n l_n
x2_1 y2_1
...
x2_m y2_m
输入输出样例
输入 #1
1 1
5 0 10
1 1 2 1 2
1 1 5 8 2
1 1 2 4 5
1 1 3 9 2
1 1 4 3 2
输出 #1
26
输入 #2
3 5
5 2 10
2 2 2 3 1
2 1 1 2 2
2 3 5 4 3
3 4 4 6 1
2 5 3 5 2
1 2
3 2
输出 #2
17
样例解释 1
即正常的多重背包问题。
样例解释 2
其一最优解路线如下：
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)
拾取的物品分别是在 (2,1) 位置上的体积 1，收益 2 的 2 个宝藏，在 (2,2) 位置上的体积 2，收益 3 的 1 个宝藏，在 (2,5) 位置上的体积 3，收益 5 的 2 个宝藏。
消耗的体积：1×2+2×1+3×2=10，刚刚好。
获得的收益：2×2+3×1+5×2=17，故输出 17。
数据范围
对于 20% 的数据，保证 a,b=1,1。对于 30% 的数据，保证 a,b≤5。另外 20% 的数据，
保证 1≤l≤2。对于100% 的数据，保证 1≤a,b≤100,0≤m≤a×b,n≤1000,1≤v,w≤10^9,1≤l≤10^6,1≤sumv≤10000
坐标合法，且所有输入为整数。
其他说明
本题目zhangjinxuan原创，测评链接 https://hydro.ac/d/gaoshan/p/FCR6maze
答案与解析
**** Hidden Message *****
最佳战士排行榜
本帖子不设本奖励。 三个GPT，全错，一分没有{:9_217:} 我为什么更这么快，因为这个本来是存粹发题解的{:10_256:}{:10_256:}{:10_256:} 这个问题可以使用动态规划来解决。首先，我们可以定义一个二维数组dp来表示从起点(1,1)到任意点(i,j)能够获得的最大收益。初始时，将dp数组的所有元素初始化为0。
然后，我们可以遍历迷宫中的每个点(i,j)，并计算从起点到该点的最大收益。对于每个点，我们需要考虑两种情况：向下移动和向右移动。
如果(i,j)是一个宝藏的位置，我们可以选择拾取该宝藏或不拾取。如果选择拾取该宝藏，我们需要判断背包是否还有足够的容量来放入该宝藏。如果有足够的容量，我们可以更新dp[ i]为拾取该宝藏后的收益加上从上一个位置(dp)到达当前位置的收益。如果没有足够的容量，我们不拾取该宝藏，dp[ i]保持不变。
如果(i,j)不是宝藏的位置，我们只需要考虑向下移动和向右移动的情况。我们可以选择从上方的位置(dp)向下移动到当前位置，或者选择从左侧的位置(dp[ i])向右移动到当前位置。我们选择其中收益更大的路径，并更新dp[ i]为该路径的收益。
最后，我们返回dp作为从起点到任意非障碍点的最大收益。
下面是具体的代码实现：
def solve(a, b, n, m, sumv, treasures, obstacles):
dp = [ * (b+1) for _ in range(a+1)]
for i in range(1, a+1):
for j in range(1, b+1):
for treasure in treasures:
x, y, v, w, l = treasure
if x == i and y == j:
for k in range(1, min(l+1, sumv//v+1)):
dp[ i] = max(dp[ i], dp + k * w)
if (i, j) not in obstacles:
dp[ i] = max(dp[ i], dp, dp[ i])
return dp
其中，treasures是一个列表，存储了每个宝藏的位置和属性。obstacles是一个集合，存储了障碍的位置。
使用上述代码，我们可以得到输入样例1的输出为26，输入样例2的输出为17。 对于这道题目，可以使用动态规划来解决。首先创建一个二维数组dp，表示到达迷宫的每个位置所能获得的最大收益。初始化dp为0。
然后，遍历迷宫的每个位置，计算到达该位置所能获得的最大收益。对于每个位置(i, j)，有两种情况：
1. 如果该位置是障碍物，则dp = -∞，表示无法到达该位置。
2. 如果该位置不是障碍物，则可以从上方位置(i-1, j)或左侧位置(i, j-1)到达该位置。根据上述两个位置的dp值，选择一条路径，使得到达该位置的总收益最大化。具体的计算方式为：
dp = max(dp, dp) + w，
其中w表示该位置上的宝藏收益。
遍历完所有位置后，dp即为从起始位置(1, 1)到达迷宫任意非障碍位置所能获得的最大收益。
以下是示例代码（使用C++）：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int a, b, n, m, sumv;
cin >> a >> b >> n >> m >> sumv;
// 创建二维数组dp，并初始化为0
vector<vector<int>> dp(a+1, vector<int>(b+1, 0));
// 遍历障碍物，将对应位置的dp值设为-∞
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
dp = -1;
}
// 遍历宝藏，更新dp值
for (int i = 0; i < n; i++) {
int x, y, v, w, l;
cin >> x >> y >> v >> w >> l;
// 多重背包问题
while (l > 0) {
int num = min(l, sumv/v); // 当前宝藏最多可以拾取的数量
l -= num; // 更新剩余数量
// 在位置(x, y)处选择拾取num个宝藏
for (int j = a; j >= x; j--) {
for (int k = b; k >= y; k--) {
if (dp != -1) {
dp = max(dp, dp + w*num);
}
}
}
sumv -= num * v; // 更新剩余背包容量
}
}
// 输出结果
cout << dp << endl;
return 0;
}
希望对你有帮助！如果还有其他问题，请随时提问。
如果回答对你有帮助，请给我一个最佳答案！这对我非常重要！{:10_254:}{:10_254:}{:10_254:}
根据题目描述和输入样例，这是一个多重背包问题。下面是解题思路和C++代码示例：
1. 定义一个二维数组dp，表示在位置(1,1)到位置(a,b)时能够获得的最大收益。
2. 初始化dp数组的第一行和第一列为0，表示只能沿着水平或垂直方向移动到达当前位置，并且此时没有获得任何宝藏，所以收益为0。
3. 遍历每个位置(i,j)，计算从起点到达位置(i,j)时的最大收益：
- 如果当前位置是障碍物，则跳过。
- 否则，考虑在当前位置能够获得的所有宝藏：
- 对于第k种宝藏，如果可以放入背包中（背包剩余容量sumv >= 宝藏体积），则更新dp为dp和dp中的较大值，分别表示不拾取当前宝藏和拾取当前宝藏的情况下的最大收益。
4. 最终结果保存在dp中，输出dp即可。
以下是C++代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Treasure {
int x; // 宝藏的行坐标
int y; // 宝藏的列坐标
int v; // 宝藏的体积
int w; // 宝藏的收益
int l; // 宝藏的数量
};
int main() {
int a, b, n, m, sumv;
cin >> a >> b >> n >> m >> sumv;
vector<vector<int>> dp(a + 1, vector<int>(b + 1, 0)); // 初始化dp数组
vector<Treasure> treasures(n);
for (int i = 0; i < n; i++) {
cin >> treasures.x >> treasures.y >> treasures.v >> treasures.w >> treasures.l;
}
vector<pair<int, int>> obstacles(m);
for (int i = 0; i < m; i++) {
cin >> obstacles.first >> obstacles.second;
}
for (int i = 1; i <= a; i++) {
for (int j = 1; j <= b; j++) {
bool isObstacle = false;
for (const auto& obstacle : obstacles) {
if (obstacle.first == i && obstacle.second == j) {
isObstacle = true;
break;
}
}
if (!isObstacle) {
for (const auto& treasure : treasures) {
if (treasure.x == i && treasure.y == j) {
for (int k = 0; k < treasure.l; k++) {
if (sumv >= treasure.v) {
dp = max(dp, dp);
dp = max(dp, dp + treasure.w);
sumv -= treasure.v;
}
}
}
}
}
}
}
cout << dp << endl;
return 0;
}
以上是求解迷宫问题的C++代码。你可以将题目给定的输入示例按照规定的格式输入到程序中，然后运行程序即可得到输出结果。
如果回答对你有帮助，请给我一个最佳答案！{:10_254:}{:10_254:}{:10_254:}
isdkz 发表于 2023-8-6 20:58
这个问题可以使用动态规划来解决。首先，我们可以定义一个二维数组dp来表示从起点(1,1)到任意点(i,j)能 ...
TLE{:9_217:} Mike_python小 发表于 2023-8-6 20:58
对于这道题目，可以使用动态规划来解决。首先创建一个二维数组dp，表示到达迷宫的每个位置所能获得的最 ...
RE{:9_217:} 学习编程中的Ben 发表于 2023-8-6 20:58
根据题目描述和输入样例，这是一个多重背包问题。下面是解题思路和C++代码示例：
1. 定义一个二维数组dp
WA{:9_217:} 你还在忙啊，加油，回去给你加工资，ppt做好，我先去睡了~· 高山 发表于 2023-8-6 21:08
你还在忙啊，加油，回去给你加工资，ppt做好，我先去睡了~·
你是说，这个题目的 ppt 还是？ zhangjinxuan 发表于 2023-8-6 21:15
你是说，这个题目的 ppt 还是？
也可以 高山 发表于 2023-8-6 21:18
也可以
那么我做好了{:9_217:}
里面有 pdf 和 word 版。
就简单改一改前面的要求就完工{:10_256:} #include <bits/stdc++.h>
using namespace std;
int n, m, a, b;
int s;
int x, y, v, w, smv, l;
long long f, ans;
struct Info {
int v, w, l;
};
vector<Info> t;
int main() {
scanf("%d%d", &a, &b);
scanf("%d%d%d", &n, &m, &smv);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d%d%d", &x, &y, &v, &w, &l);
t.push_back({v, w, l});
}
for (int j = 1; j <= m; ++j) {
scanf("%d%d", &x, &y);
s = -1;
}
for (int i = 1; i <= a; ++i) {
for (int j = 1; j <= b; ++j) {
if (s == -1) continue;
int li = (i - 1) % 5;
int ri = i % 5;
int lj = j - 1;
int rj = j;
for (int k = 0; k <= smv; ++k) {
long long tmp = 0;
if (s != -1) {
tmp = max(f, tmp);
}
if (s != -1) {
tmp = max(f, tmp);
}
f = max(f, tmp);
}
for (auto th : t) {
int c = {}, tot = 0, tmp = 1;
while (th.l >= tmp) {
c[++tot] = tmp;
th.l -= tmp;
tmp *= 2;
}
if (th.l) c[++tot] = th.l;
for (int ii = 1; ii <= tot; ++ii) {
for (int k = smv; k >= 1ll * th.v * c; --k) {
f = max(f, f] + th.w * c);
}
}
}
ans = max(ans, f);
}
}
printf("%lld", ans);
return 0;
}
AC{:9_217:} Mike_python小 发表于 2023-8-6 21:28
AC
与 std 代码相似度 99%，视为抄袭{:10_256:} 哈哈哈 zhangjinxuan 发表于 2023-8-6 18:31
与 std 代码相似度 99%，视为抄袭
{:9_233:} 55
{:10_266:}
页:
[1]