2022CCPC威海 D. Sternhalma（记忆化搜索/状压）

题意大概是给定一个19个格子的六边形棋盘，每个位置有一个分数，每次操作可以拿走一个棋子（不得分）或者将当前棋子跳过相邻的一个棋子（得分为跳过的棋子所在位置的分数）且将跳过的棋子拿走，问分数最大是多少。

记忆化搜索+状压。因为只有19个位置，因此可以用一个int整数表示状态，同时注意到是一个棋盘对应多种摆放顺序，因此联想到记忆化。这个题的难点在于棋盘是六边形，枚举转移较为麻烦。

#include <bits/stdc++.h>
using namespace std;
int score[5][5], n;
int vis[(1 << 20) + 5];
int Pos[5][5] = {//Pos[i][j]表示i, j这个位置对应在状态中的下标
	{0, 1, 2},
	{3, 4, 5, 6},
	{7, 8, 9, 10, 11},
	{12, 13, 14, 15},
	{16, 17, 18},
};
int d1[5][6][2] = {//d1[i]表示第i行的位置往六个方向移动一格的坐标增量
	{
		{-1, -1}, {-1, 0}, {0, -1}, {0, 1}, {1, 0}, {1, 1},
	},
	{
		{-1, -1}, {-1, 0}, {0, -1}, {0, 1}, {1, 0}, {1, 1},
	},
	{
		{-1, -1}, {-1, 0}, {0, -1}, {0, 1}, {1, -1}, {1, 0},
	},
	{
		{-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0},
	},
	{	
		{-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0},
	}
};
int d2[5][6][2] = {//d2[i]表示第i行的位置往六个方向移动两格的坐标增量
	{
		{-2, -2}, {-2, 0}, {0, -2}, {0, 2}, {2, 0}, {2, 2},
	},
	{
		{-2, -2}, {-2, 0}, {0, -2}, {0, 2}, {2, -1}, {2, 1},
	},
	{
		{-2, -2}, {-2, 0}, {0, -2}, {0, 2}, {2, -2}, {2, 0},
	},
	{
		{-2, -1}, {-2, 1}, {0, -2}, {0, 2}, {2, -2}, {2, 0},
	},
	{	
		{-2, 0}, {-2, 2}, {0, -2}, {0, 2}, {2, -2}, {2, 0},
	}
};
int limit[5] = {2, 3, 4, 3, 2};//每行数的个数
int getStat(string s) {
	int ans = 0;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == '#') {
			ans |= (1 << i);
		}
	}
	return ans;
}
int dfs(int stat, int step) {
	if(vis[stat] != -0x3f3f3f3f) return vis[stat];
	int ans = 0;
	int mp[5][5];
	for(int i = 0; i < 5; i++) {
		for(int j = 0; j < 5; j++) {
			mp[i][j] = 0;
		}
	}
	int one = 0;
	for(int i = 0; i < 19; i++) {
		if((stat >> i) & 1) {
			//第一种操作
			one++;
			ans = max(ans, dfs(stat & (~(1 << i)), step));
			if(i >= 0 && i <= 2) {
				mp[0][i] = 1;
			} else if(i >= 3 && i <= 6) {
				mp[1][i - 3] = 1;
			} else if(i >= 7 && i <= 11) {
				mp[2][i - 7] = 1;
			} else if(i >= 12 && i <= 15) {
				mp[3][i - 12] = 1;
			} else {
				mp[4][i - 16] = 1;
			}
		}
	}
	for(int i = 0; i < 5; i++) {
		for(int j = 0; j <= limit[i]; j++) {
			if(!mp[i][j]) continue;
			int nowx = i, nowy = j;
			for(int k = 0; k < 6; k++) {
				int nx1 = nowx + d1[i][k][0], ny1 = nowy + d1[i][k][1];//要跨过的点
				int nx2 = nowx + d2[i][k][0], ny2 = nowy + d2[i][k][1];//落点
				if(nx1 < 0 || nx1 >= 5 || ny1 < 0 || ny1 > limit[nx1]) continue;//短路 所以不会出现nx1越界的情况
				if(nx2 < 0 || nx2 >= 5 || ny2 < 0 || ny2 > limit[nx2]) continue;
				if(!mp[nx1][ny1]) continue;
				if(mp[nx2][ny2]) continue;
				int nxt_stat = stat;
				nxt_stat &= (~(1 << Pos[nowx][nowy]));//构造下一个状态 首先清除当前位置
				nxt_stat &= (~(1 << Pos[nx1][ny1]));//清除跳过的位置
				nxt_stat |= (1 << (Pos[nx2][ny2]));//跳到的位置设为1
				ans = max(ans, score[nx1][ny1] + dfs(nxt_stat, step + 1));
			}
		}
	}
	vis[stat] = ans;
	return ans;
}
int main() {
	for(int i = 0; i < 5; i++) {
		for(int j = 0; j <= limit[i]; j++) {
			cin >> score[i][j];
		}
	}
	cin >> n;
	for(int i = 0; i < (1 << 20); i++) {
		vis[i] = -0x3f3f3f3f;
	}
	for(int i = 1; i <= n; i++) {
		string s = "";
		for(int j = 1; j <= 5; j++) {
			string tmp;
			cin >> tmp;
			s += tmp;
		}
		cout << dfs(getStat(s), 1) << endl;
	}
	return 0;
}