[CF1296E2] String Coloring (hard version) - dp
Description
给定字符串,每个位置染上一种不大于 n 的颜色,相邻位置如果颜色不同则可以交换位置,要求交换若干次后按字典序排序。求颜色数最少的染色方案。
Solution
每个字母最后被换到的位置是确定了
一路上所有的字母得跟他颜色不同
于是逆序对的颜色都是不同的,否则无要求
设 (f[i]) 表示 ([i,n]) 中 i 开头的最长下降子序列长度,那么我们将 (f[i]) 作为 i 的颜色,就可以保证所有逆序对颜色不相同
如果逆序对 i,j 颜色相同,那么我们可以构造 i->j 的转移,使得 (f[j]) 增大,矛盾
现在问题是怎么求每个位置开头的 LDS 长度
一个显然的暴力是,倒序扫描,找每个最近的更小字母位置
但与其记录字母位置,不如直接记录每个更小字母已经有过的最大长度,然后直接续上
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
string str;
cin >> str;
str = "0" + str;
vector<int> f(n + 2);
vector<int> mx(128);
int ans = 0;
for (int i = n; i >= 1; i--)
{
for (int j = str[i] - 1; j >= 'a' - 1; j--)
f[i] = max(f[i], mx[j] + 1);
mx[str[i]] = max(mx[str[i]], f[i]);
ans = max(ans, f[i]);
}
cout << ans << endl;
for (int i = 1; i <= n; i++)
cout << f[i] << " ";
}