QOJ5013 Astral Birth（凸包，分治，堆，贪心）

QOJ5013 Astral Birth

\(m = 1\) 直接求 LIS。

否则对于 \(m \ge 2\)，就是求把序列分成 \(m + 1\) 段，每段翻转或者不翻转，最终最多 \(1\) 的个数。

很明显相邻两段翻不翻转的选择是互异的。

做法 1：容易发现最多的 \(1\) 个数和段数的关系是个凸包，所以可以分治合并凸包 DP。

做法 2：刚开始先按初始颜色分段。枚举最左、最右的段的选择（\(4\) 种），如果和当前不同就把当前端点段翻转和相邻段合并。贪心，每次选择不是端点段的最短的段 \(x\)，和两边的段 \(y, z\) 合并（段数 \(-2\)），变成颜色和两边一样，长度为 \(y + z - x\) 的段。可以用堆或桶维护，时间复杂度最低 \(\Theta(n)\)。

错因：没有对左右端的选择分类，而是选择强行处理细节。

代码

#include <bits/stdc++.h>
using namespace std;

template<typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto& x : v) {
		if (!first) res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}

void debug_out() { cerr << "\n"; }

template<typename U, typename... T>
void debug_out(const U& x, const T&... args) {
	cerr << " " << to_string(x);
	debug_out(args...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) // debugrs

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	string s;
	cin >> n >> s;
	vector<int> sum(n + 1, 0);
	for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + (s[i] == '1');
	vector<int> f(n + 1, 0);
	for (int i = 0; i <= n; ++i) f[1] = max(f[1], (i - sum[i]) + (sum[n] - sum[i]));
	vector<int> S;
	for (int L = 0, r; L < n; L = r) {
		r = L + 1;
		while (r < n and s[r] == s[L]) ++r;
		S.emplace_back(r - L);
	}
	int ns = S.size();
	fill(f.begin() + max(2, ns - 1), f.end(), n);
	if (ns >= 4) for (int X : {0, 1}) for (int Y : {0, 1}) {
		vector<int> ls(ns + 1), rs(ns + 1), len(ns), del(ns, false);
		auto delet = [&](int i) {
			rs[ls[i]] = rs[i];
			ls[rs[i]] = ls[i];
			del[i] = true;
		};
		vector<vector<int>> V(n + 1);
		for (int i = 0; i < ns; ++i) {
			ls[i] = i == 0 ? ns : i - 1;
			rs[i] = i == ns - 1 ? ns : i + 1;
			len[i] = S[i];
		}
		ls[ns] = ns - 1;
		rs[ns] = 0;
		int k = ns, cur = n;
		if (s[0] - '0' != X) {
			k -= 1;
			cur -= S[0];
			delet(0);
		}
		if (s[n - 1] - '0' != Y) {
			k -= 1;
			cur -= S[ns - 1];
			delet(ns - 1);
		}
		if (k >= 3) f[k - 1] = max(f[k - 1], cur);
		for (int i = 0; i < ns; ++i) if (ls[i] != ns and rs[i] != ns) V[len[i]].push_back(i);
		for (int L = 1; L <= n and k >= 4; ++L) while (V[L].size() and k >= 4) {
			int i = V[L].back();
			V[L].pop_back();
			if (del[i]) continue;
			// debug(L, i);
			cur -= L;
			len[i] = len[ls[i]] + len[rs[i]] - len[i];
			delet(ls[i]);
			delet(rs[i]);
			if (k >= 4) f[k - 2] = max(f[k - 2], cur);
			if (k >= 5) f[k - 3] = max(f[k - 3], cur);
			k -= 2;
			if (ls[i] != ns and rs[i] != ns) V[len[i]].push_back(i);
		}
	}
	for (int i = 1; i <= n; ++i) cout << f[i] << ' ';
	cout << '\n';
}