2021CCPC河南省 欢度佳节

http://acm.zzuli.edu.cn/problem.php?id=2827

思路

一共17个格子, 每次只能走相邻的, 求能走的最长路径。

解法1：建图 从起点开始标号, 当A与B相邻时, 从A到B连一条权值为B的边, 从B到A连一条权值为A的边。

然后直接DFS开搜, 用st来保存当前路径上走过的点。 假设每次筛子都投6, 通过处理, 把每个点的权值从糖果数改为最少扔筛子数即可, (w[i] + 5) / 6

解法2：状态压缩 一共17个格子, 故可以用二进制来表示每个格子是否选中。 2^17 == 131072 不会超时。

对于每个位置用DFS来搜索判断该状态是否不成立。

代码

解法2

#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
#define int long long
using namespace std;
const int N = 20, mod = 1e9 + 7;
int n;
int a[18];
int w[N];
int arrive, cnt;
int x[] = {1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5};
int y[] = {1, 2, 4, 5, 2, 3, 4, 2, 3, 4, 2, 3, 4, 1, 2, 4, 5};
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int mp[10][10];
 
bool dfs(int x, int y, int state)
{
	if(arrive == state && cnt <= n) return true;
	int id = mp[x][y];
 
	if(id == -1 || !(state >> id & 1) || (arrive >> id & 1)) return false;
 
	arrive |= 1 << id;
	cnt += w[id];
 
	for(int i = 0; i < 4; i++)
	{
		if(dfs(x + dx[i], y + dy[i], state))
			return true;
	}
	return false;
}
 
main()
{
	memset(mp, -1, sizeof mp);
	for (int i = 0; i < 17; i++)
		mp[x[i]][y[i]] = i;
	int T;
	cin >> T;
	while (T--)
	{
		for (int i = 0; i < 17; i++)
			cin >> w[i], w[i] = (w[i] + 5) / 6;
		cin >> n;
		int res = 0;
		for (int i = 0; i < 1 << 17; i++)
		{
			if (i >> 13 & 1 == 0)
				continue;
			arrive = 0, cnt = 0;
			if (dfs(x[13], y[13], i))
				res = max(res, __builtin_popcount(i));
		}
		cout << res << endl;
	}
	return 0;
}