题目来源:2022 China Collegiate Programming Contest Weihai Site D – Sternhalma
题目链接:https://codeforces.com/gym/104023/problem/D
题意
在一个\(19\)个格子的六边形棋盘上,每个格子有一个固定的权值 \(w_i\),格子上可以放置棋子。
可以进行以下两种操作:
- 移除某个格子上的棋子,获得 \(0\) 权值.
- 将一个棋子,以与他相邻的棋子作为跳板,跳到对称位置,跳跃后,作为跳板的棋子被移除,并获得跳板棋子所在格子的权值 \(w_i\).
有 \(t\) 组案例,每组案例给出棋子的放置情况,要求输出最大能获得的权值和。
数据范围:\(-10^6 \le w_i \le 10^6\),\(1 \le t \le 10^4\).
思路:状压dp + 记忆化搜索
由于格子的数量只有 \(19\) 个,考虑状态压缩,第 \(i\) 位为 \(0/1\) 表示第 \(i\) 个格子 无/有 棋子。
记当前状态为 \(state\),其第 \(i\) 位为 \(state_i\),其能获得的最大权值和为 \(f[state]\),则
-
对于操作一
若有 \(state_i = 1\),有转移 \(f[state] = max(f[state], f[state-2^i])\).
-
对于操作二
若有 \(state_i = 1\),记格子 \(i\) 做跳板时,跳跃前后的格子为 \(a\),\(b\),若有\(state_a = 1\ and\ state_b = 0\),则有转移 \(f[state] = max(f[state], f[state – 2^i – 2^a + 2^b])\).
为了方便转移,我们可以先将每个格子做跳板时,合法的跳跃前后的格子对,预处理出来。
因为格子的权值固定,因此可以用记忆化搜索。
时间复杂度:\(O(t·n + 2^n)\),其中 \(n=19\).
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 19;
int w[N], f[1 << N], vis[1 << N];
vector<pair<int,int>> v[N]; // v[i]:格子i作为跳板时,合法的跳跃前后格子
// 跳板格子,以及跳跃前后的两个格子
void add(int mid, int a, int b)
{
v[mid].push_back({a, b});
v[mid].push_back({b, a});
}
int dfs(int state)
{
if(vis[state]) return f[state];
// Remove
for(int i = 0; i < N; ++ i) {
if(!(state >> i & 1)) continue;
f[state] = max(f[state], dfs(state - (1 << i)));
}
// Remove by jumping
for(int i = 0; i < N; ++ i) {
if(!(state >> i & 1)) continue;
for(auto p : v[i]) {
int a = p.first, b = p.second;
if(!(state >> a & 1) || (state >> b & 1)) continue;
f[state] = max(f[state], dfs(state - (1 << i) - (1 << a) + (1 << b)) + w[i]);
}
}
vis[state] = 1;
return f[state];
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
for(int i = 0; i < N; ++ i) cin >> w[i];
memset(f, -0x3f, sizeof f);
f[0] = 0, vis[0] = 1;
add(1, 0, 2);
add(3, 0, 7);
add(4, 0, 9), add(4, 1, 8), add(4, 3, 5);
add(5, 1, 10), add(5, 2, 9), add(5, 4, 6);
add(6, 2, 11);
add(8, 3, 13), add(8, 4, 12), add(8, 7, 9);
add(9, 4, 14), add(9, 5, 13), add(9, 8, 10);
add(10, 5, 15), add(10, 6, 14), add(10, 9, 11);
add(12, 7, 16);
add(13, 8, 17), add(13, 9, 16), add(13, 12, 14);
add(14, 9, 18), add(14, 10, 17), add(14, 13, 15);
add(15, 11, 18);
add(17, 16, 18);
int test;
cin >> test;
while(test--) {
string s, t;
for(int i = 0; i < 5; ++ i) cin >> t, s += t;
int state = 0;
for(int i = 0; i < N; ++ i) {
if(s[i] == '#') state += 1 << i;
}
cout << dfs(state) << endl;
}
return 0;
}
原文地址:http://www.cnblogs.com/jakon/p/16891052.html