评测记录：https://www.luogu.com.cn/record/201533796

复杂度应该是正确的。自测极限数据（$N=6,D=100$）跑了 2.7s。

// Problem: 
//     P3999 [SHOI2013] 二重镇
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3999
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

int n, d, a[110];
int p[10];

inline int get(const int x, const int y) { // x 的第 y 位
	return x / p[y] % 6;
}

inline int work(const int x, const int y, const int z) {
	return x - get(x, y) * p[y] + z * p[y];
}

pair<int, int> jyh[279936][6];

inline pair<int, int> change(int x, const int y, const int z) {		// 将 x 的第 y 位改为 z，并合并
	x = work(x, y, z);
	
	int res = 0;
	
	auto &ans = jyh[x][y];
	if (~ans.first) return ans;
	
	bool flg = true;
	while (flg) {
		flg = false;
		
		int z = get(x, y);
		if (!z) continue;
		
		int L, R;
		for (L = y - 1; ~L && get(x, L) == z; -- L );
		for (R = y + 1; R < n && get(x, R) == z; ++ R );
		L ++, R -- ;
		
		if (R - L + 1 >= 2) {
			flg = true;
			res += (1 << z) * (R - L + 1);
			for (int i = L; i <= R; ++ i ) {
				x = work(x, i, (z == 5 || i != y) ? 0 : z + 1);
			}
		}
	}
	
	return ans = {x, res};
}

int f[279936][101];

inline int dp(const int S, const int x) {
	// 现在是第 x 天，每个格子+仓库的状态为 S，接下来最大收益是多少
	if (x > d + 1) return 0;
	if (~f[S][x]) return f[S][x];
	
	f[S][x] = 0;
	auto check = [&](const int y) {
		f[S][x] = f[S][x] > y ? f[S][x] : y;
	};
	
	for (int i = 0; i < n; ++ i )
		if (!get(S, i)) {
			auto [newS, w] = change(S, i, a[x]);
			check(dp(newS, x + 1) + w);
		}
	
	const int t = get(S, n);
	if (t == 0) check(dp(work(S, n, a[x]), x + 1));
	else {
		for (int i = 0; i < n; ++ i )
			if (!get(S, i)) {
				const auto [newS1, w1] = change(work(S, n, 0), i, t);
				check(dp(newS1, x) + w1);
			}
	}
	
	return f[S][x];
}

signed main() {
	p[0] = 1;
	for (int i = 1; i < 10; ++ i ) p[i] = p[i - 1] * 6;

	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> d;
	for (int i = 1; i <= d; ++ i ) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	
	memset(f, -1, sizeof f);
	memset(jyh, -1, sizeof jyh);
	cout << dp(0, 1);
	
	return 0;
}