首页 > 其他分享 >P3519 [POI2011]ROZ-Difference

P3519 [POI2011]ROZ-Difference

时间:2023-07-02 15:00:48浏览次数:53  
标签:cnt ch POI2011 ROZ P3519 Difference

考虑枚举最大的字母所处的位置 \(i\) 作为端点和最小的字母 \(j\)。

然后就有记录一下前缀出现次数 \(cnt\),枚举一个区间。

\[cnt_{i, ch_i} - cnt_{i, j} - (cnt_{i',ch_i} -cnt_{i', j}) \]

求这个式子最大值。显然这两个式子相似,记录一下关于 \(ch_i\) 的 \(cnt\) 前缀最小值即可。

大概是 \(O(26n)\) 的。

代码自己去贺题解区的,写的都比我好。

标签:cnt,ch,POI2011,ROZ,P3519,Difference
From: https://www.cnblogs.com/Custlo/p/17520808.html

相关文章