题解：P11447 「ALFR Round 3」C 割

思路

不难想到一个性质：字符串

S

的字典序最大的子序列，一定为以其最大字符首次出现的位置为起点的，单调不增序列。所以考虑到使用单调栈维护。显然，当

k=1

时，把整个字符串从头到尾维护一遍的结果就是答案。

现在要分成

k

段，可以先把几个最大字符的位置存出来。设有

cnt

个最大字符，一个容易想到的结论是，最佳的分割方式的分割点一定在这些最大字符之后紧邻的一个位置。因为每个最大字符，都一定会成为它所在小段

s

的最大字典序子序列

f(s)

的一部分。在其之后紧邻的一个位置分割，就保证了

f(s)

最后一位也是最大字符，没有了后面的冗余字符来使其字典序增大。这样，

f(s)

就仅由最大字符构成。

那么，问题就转化为将

cnt

个最大字符放入

k

个序列中。要求最小的分割方式权值，就要使最大字符最多的序列中最大字符的数量尽量少。换句话说，最佳的分配方式是按抽屉原理，平均地分配最大字符。这时还需要分类：

当 $cnt$ 不能被 $k$ 整除时，最大字符最多的区间 $s$ 的 $f(s)$ 就有 $\lceil\frac{cnt}{k}\rceil$ 个字符。此时我们可以将该区间放在前面，最终答案就是 $\lceil\frac{cnt}{k}\rceil$ 个最大字符；
当能整除时，因为需要平均分配，所以这整个字符串最后一个最大字符的末尾就没有分割点。此时，最后一个最大字符后面还有冗余字符，需要再跑一遍单调栈，把这些冗余字符组成的串的最大字典序子序列拼接在 $\frac{cnt}{k}$ 个最大字符之后。

总结：最终答案为 $\lceil\frac{cnt}{k}\rceil$ 个最大字符。若能整除，则再跑一遍单调栈，把尾巴的最大字典序子序列拼接在后面。

code

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,pos[200001],cnt,top;
string s,ans1,ans2;
char maxx,stk[200001];
void ddz(int begin)//单调栈求以 begin 为起点的最大字典序子序列 
{
	for(int i=begin; i<n; i++)
	{
		while(top && stk[top]<s[i]){top--;}
		stk[++top]=s[i];
	}
	for(int i=1; i<=top; i++)
		cout<<stk[i];
}
int main()
{
	cin>>n>>k>>s; 
	for(int i=0; i<n; i++)
		maxx=max(s[i],maxx);
	for(int i=0; i<n; i++)
		if(s[i]==maxx) pos[++cnt]=i;
	if(k==1){
		ddz(0);
		return 0;
	}
	for(int i=1; i<=ceil(cnt*1.0/k); i++)
		cout<<maxx;
	if(cnt%k==0)//能整分，最后一段需要再求一次 
		ddz(pos[cnt]+1);
	return 0;
}

题解：P11447 「ALFR Round 3」C 割

文章操作

思路

code

相关推荐

评论

题解：P11447 「ALFR Round 3」C 割