提供一篇搜索题解。

思路

观察题目发现

1 \le k \le 10

并且

a_i \le 3

，那么所有的有鱼的格点状态就只有

4^k

种，可以接受，所以我们可以定义一个 10 维数组来做状态减枝（我也是第一次定义那么多维的数组-_-||）。

然后就是怎么搜索了。我们枚举每个未被取完的有鱼的格子，要取到某个格子的鱼，我们可以有五个位置：上下左右中。枚举到一个格点

p_i

后，我们也把

p_i

的上下左右中减去我们要取的数量即可。

代码

CPP

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define PII pair<int, int>
#define x first
#define y second
#define cur (dp[arr[0]][arr[1]][arr[2]][arr[3]]\
[arr[4]][arr[5]][arr[6]][arr[7]][arr[8]][arr[9]])
int arr[15] = { 0 };
int dp[4][4][4][4][4][4][4][4][4][4] = { 0 };
int n, m, k;
PII pos[15];
int dir[5][2] = {
	{ 0, 0 }, { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }
};
void dfs(int step) {
	if (step >= cur) return;
	cur = step;
	vector<int> brr(k);
	for (int c = 0; c < k; c++)
		if (arr[c]) {
			int cnt = arr[c];
			for (int d = 0; d < 5; d++) {
				int x = pos[c].x + dir[d][0],
					y = pos[c].y + dir[d][1];
				for (int i = 0; i < 5; i++) {
					int dx = x + dir[i][0],
						dy = y + dir[i][1];
					for (int j = 0; j < k; j++)
						if (dx == pos[j].x && dy == pos[j].y) {
							brr[j] = arr[j];
							arr[j] = max(0, arr[j] - cnt);
						}
				}
				dfs(step + cnt);
				for (int i = 0; i < 5; i++) {
					int dx = x + dir[i][0],
						dy = y + dir[i][1];
					for (int j = 0; j < k; j++)
						if (dx == pos[j].x && dy == pos[j].y) arr[j] = brr[j];
				}
			}
		}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < k; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		pos[i] = { x, y };
		arr[i] = z;
	}
	memset(dp, 0x3f, sizeof dp);
	dfs(0);
	printf("%d", dp[0][0][0][0][0][0][0][0][0][0]);
	return 0;
}

题解：P10865 [HBCPC2024] Genshin Impact Startup Forbidden III

文章操作

思路

代码

相关推荐

评论

题解：P10865 [HBCPC2024] Genshin Impact Startup Forbidden III