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

using namespace std;

template

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

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 sum(n + 1, 0);

for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + (s[i] == '1');

vector f(n + 1, 0);

for (int i = 0; i <= n; ++i) f[1] = max(f[1], (i - sum[i]) + (sum[n] - sum[i]));

vector 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 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> 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';

}

查看原文