P3339
一道十分甚至九分难写的状压DP。
数据范围明显告诉我们此题可以六进制压缩村庄状态。
由于合并规则的存在，可以先预处理出在 pos 处插入 k 时转移至的状态以及这样做得到的分数。
设当前状态为S ，转移至的状态为to，所得分数为val。
就有转移：
\[dp[to[S][pos][a[day]]][stored][day] = \max{dp[S][stored][day - 1]}\\
dp[to[S][pos][stored]][a[day]][day] = \max{dp[S][stored][day - 1]}\\
dp[S][a[day]][day] = \max{dp[S][stored][day - 1]}
\]
值得注意的是虽然合成会进行多次，但是至多进行两次，因为高一级的物品会放在后放的格子上，所以放入的物品只能与其前后的物品合成。
具体实现可以看以下代码
code
// Copyright yoursluo 2023
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
const int N = 25005;
int n, d, a[105];
char s[105];
int f[N][7][105], pos[47000];
int state[N], tot, to[N][7][7], val[N][7][7];
int pw[] = {1, 6, 36, 216, 1296, 7776, 46656};
int v[10], tp, w[10];
std::vector<int> num;
inline int max(int a, int b) { return a > b ? a : b; }
inline void maxeq(int &a, int b) { a = max(a, b); }
inline void six_print(int x) {
num.clear();
int p = n - 1, cnt = 0;
while (p >= 0) {
cnt = 0;
while (x >= pw[p])
cnt++, x -= pw[p];
num.push_back(cnt);
p--;
}
for (int i : num) {
printf("%d ", i);
}
puts("");
}
inline bool ck(int x) {
memset(v, 0, sizeof(v));
v[0] = -1;
tp = 0;
int p = n - 1;
int cnt;
while (p >= 0) {
cnt = 0;
while (x >= pw[p])
cnt++, x -= pw[p];
p--;
v[++tp] = cnt;
}
cnt = -1;
for (int i = 1; i <= tp; ++i) {
int tmp = v[i];
if (tmp == cnt && tmp != 0)
return 0;
cnt = tmp;
}
return 1;
}
inline int calc(int p, int &val) {
memcpy(w, v, sizeof(w));
val = 0;
if (w[p - 1] == w[p] && w[p] == w[p + 1])
w[p - 1] = w[p + 1] = 0, val += 3 * (1 << w[p]), w[p]++;
if (w[p - 1] == w[p] && w[p] != 0)
w[p - 1] = 0, val += 2 * (1 << w[p]), w[p]++;
if (w[p] == w[p + 1] && w[p] != 0)
w[p + 1] = 0, val += 2 * (1 << w[p]), w[p]++;
if (w[p] == 6)
w[p] = 0;
if (w[p - 1] == w[p] && w[p] != 0)
w[p - 1] = 0, val += 2 * (1 << w[p]), w[p]++;
if (w[p] == s[p + 1] && w[p] != 0)
w[p + 1] = 0, val += 2 * (1 << w[p]), w[p]++;
int a = 0;
if (w[p] == 6)
w[p] = 0;
for (int i = 1; i <= tp; ++i)
a += w[i] * pw[tp - i];
return pos[a];
}
inline void prewk(int x) {
memset(v, 0, sizeof(v));
v[0] = -1;
tp = 0;
int p = n - 1, r = pos[x];
int cnt;
while (p >= 0) {
cnt = 0;
while (x >= pw[p])
cnt++, x -= pw[p];
p--;
v[++tp] = cnt;
}
tp = n;
for (int i = 1; i <= tp; ++i) {
if (v[i] == 0) {
for (int j = 1; j < 6; ++j) {
v[i] = j;
to[r][j][i] = calc(i, val[r][j][i]);
}
v[i] = 0;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
v[0] = -1;
scanf("%d%d", &n, &d);
scanf("%s", s);
for (int i = 1; i <= d; ++i)
a[i] = s[i - 1] - '0';
for (int i = 0; i < pw[n]; ++i) {
if (ck(i))
state[++tot] = i, pos[i] = tot;
}
for (int i = 1; i <= tot; ++i) {
prewk(state[i]);
}
memset(f, -1, sizeof(f));
int ans = 0;
f[1][0][0] = 0;
for (int i = 0; i <= d; ++i)
for (int k = 5; k >= 0; --k)
for (int j = 1; j <= tot; ++j) {
if (f[j][k][i] >= 0) {
if (i < d) {
for (int l = 1; l <= n; ++l) {
if (to[j][a[i + 1]][l]) {
maxeq(f[to[j][a[i + 1]][l]][k][i + 1],
f[j][k][i] + val[j][a[i + 1]][l]);
}
}
}
if (k) {
for (int l = 1; l <= n; ++l)
if (to[j][k][l]) {
maxeq(f[to[j][k][l]][0][i],
f[j][k][i] + val[j][k][l]);
}
} else {
maxeq(f[j][a[i + 1]][i + 1], f[j][k][i]);
}
maxeq(ans, f[j][k][i]);
}
}
printf("%d\n", ans);
return 0;
}