题解 CF1296E2 【String Coloring (hard version)】

ix35 · 2020-02-05 10:19:28 · 题解

根据逆序对那套理论，要通过相邻数交换使得序列有序，每一组逆序对必须要交换一次。

所以事实上题目的要求就是如果两个下标 i,j 满足 i<j 并且 S_i>S_j，那么 col_i\ne col_j，col_i 表示 i 的颜色。

如果对这个模型比较熟悉的话，可以发现它和最长下降子序列有关。

在一个下降子序列 S_{a_1},\cdots,S_{a_k} 中，因为有 S_{a_1}>S_{a_i}\ \ (i>1)，所以所有的 a_i\ \ (i>1) 的颜色都和 a_1 不同，同样的，所有 a_i\ \ (i>2) 的颜色都和 a_2 不同，于是我们可以直接得到：下降子序列中元素的颜色两两不同。

因此不同颜色的数量不小于最长下降子序列的长度，下面证明：存在一种染色方案，使得不同颜色的数量等于最长下降子序列的长度。

令 dp(i) 表示后缀 [i,n] 中以 i 开头的最长下降子序列长度，令 i 的颜色为 dp(i)，下面论证这种染色方案合法。

对于任意一组逆序对 (i,j)，显然有 dp(i)\ge dp(j)+1，因为 j 是 i 的转移之一，于是有 dp(i)\ne dp(j)，保证了逆序对的颜色不相同。

于是我们得到了一组最小染色方案。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int n,ans,dp[MAXN],mx[27];
char c[MAXN];
int main () {
    scanf("%d%s",&n,c+1);
    for (int i=n;i>=1;i--) {
        dp[i]=mx[c[i]-'a']+1;
        for (int j=c[i]-'a'+1;j<=25;j++) {mx[j]=max(mx[j],dp[i]);}
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    for (int i=1;i<n;i++) {printf("%d ",dp[i]);}
    printf("%d\n",dp[n]);
    return 0;
}