给定长为 \(n\) 的 01 字符串 \(s\), 求一个最大的 \(k\), 使得能选出 \(k\) 个形如 \([l_i,r_i]\) 的区间, 满足:
- \(\forall i\in [2,k], l_i\gt r_{i-1}\).
- \(\forall i\in [2,k]\), \(s_{l_i\sim r_i}\) 的字典序严格大于 \(s_{l_{i-1}\sim r_{i-1}}\).
\(1\le n\le 2.5\times 10^4\), 4s, 512mb.
想了八百万年贪心, 不会, 这种字符串最优化题看来大概率不是贪心!
首先, 设计一个 naive 的 dp: 将所有字串排序, 预处理出每个子串前面第一个和它不同的子串, 然后树状数组优化 dp, \(\mathcal O(n^2\log n)\).
考虑一个显然的性质: 相邻两子串的长度差距不超过 1.
这个还是比较显然的, 从贪心的角度容易理解, 我很早就看出来了这条性质, 但是没敢往 dp 想. 事实证明要大胆一点!
根据这个性质, 最长的子串长度不超过 \(\sqrt{2n}\), 那么把 \(\mathcal O(n\sqrt n)\) 个子串扔到上面那个 dp 跑就行. 时间复杂度 \(\mathcal O(n\sqrt n\log n)\).
总结点经验, 字符串相关最优化问题, 一般都是根据其松散的结构找性质 (比如这个题状态数较少这点), 或者用二分转化为判定 (本题判定也不简单, 所以这个思路在这里行不通).
// Problem: Ex - Sequence of Substrings
// Contest: AtCoder - AtCoder Beginner Contest 240
// URL: https://atcoder.jp/contests/abc240/tasks/abc240_h
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
using pii = std::pair<int, int>;
const int maxn = 1e5 + 5;
const int maxm = 6e6 + 5;
int m, tr[maxm][2], sz, n, lst[maxm], cnt;
char s[maxn];
std::vector<int> L[maxn], R[maxn];
std::vector<pii> Z[maxm];
void insert(int l, int r) {
int u = 0;
for(int i = l;i <= r;++ i) {
int c = s[i] ^ '0';
if(!tr[u][c])
tr[u][c] = ++ sz;
u = tr[u][c];
Z[u].pb(l, i);
}
return ;
}
void dfs(int u) {
int tmp = cnt;
for(auto& [l, r] : Z[u]) {
lst[++ cnt] = tmp;
L[l].pb(cnt);
R[r].pb(cnt);
}
if(tr[u][0])
dfs(tr[u][0]);
if(tr[u][1])
dfs(tr[u][1]);
return ;
}
int c[maxm], dp[maxm];
int lowbit(int x) {
return x & -x;
}
void modify(int x, int y) {
for(;x <= cnt;x += lowbit(x))
c[x] = std::max(c[x], y);
return ;
}
int query(int x) {
int ans = 0;
for(;x;x -= lowbit(x))
ans = std::max(ans, c[x]);
return ans;
}
int main() {
scanf("%d %s", &n, s + 1);
m = (int)std::sqrt(2 * n);
for(int i = 1;i <= n;++ i)
insert(i, std::min(i + m - 1, n));
dfs(0);
int ans = 0;
for(int i = 1;i <= n;++ i) {
for(auto& x : L[i])
ans = std::max(ans, dp[x] = query(lst[x]) + 1);
for(auto& x : R[i])
modify(x, dp[x]);
}
printf("%d\n", ans);
return 0;
}