自动搬运

查看原文

来自洛谷，原作者为

	lnwhl AFO

搬运于2025-08-24 22:46:11，当前版本为作者最后更新于2023-05-03 15:01:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设字符串的长度为 $n$。

dp，$f[i][j][k]$ 表示 $s[1\dots i]$ 通过删去若干字符，能够凑出 $j$ 个完整的 bessie，最后一个（不完整的） bessie 已经凑齐了前 $k$ 位的最小删除代价和。答案即为最大的 $j$ 和对应的 $f[n][j][0]$。

考虑如何转移：

1. 删除 $s[i]$，$f[i][j][k]=f[i-1][j][k]+c[i]$。
2. 如果 $s[i]$ 等于 bessie 中的第 $k$ 个字母，那么 $f[i][j][k]=f[i-1][j][k-1]$，不需要转移代价。

如上两种转移取最优即可。

但是我们还需要考虑 $k=0$ 的 Corner Case：

1. 对于第一个转移，因为出现了 bessie 中的前 $0$ 个字母并非真实存在，所以并不需要删除字母来维护这个条件（字母就放在那里即可），$f[i][j][0]$ 可以由 $f[i-1][j][0]$ 直接转移而来，无需转移代价。
2. 对于第二个转移，$f[i][j][0]$ 可以直接由 $f[i][j-1][6]$ 转移而来，也无需转移代价。

这样我们就得到了一个 $\mathcal O(n^2)$ 的解法，可以通过 $n\le 2000$ 的 Subtask。考虑优化。

考虑把 $j$ 踢出状态，$f[i][k]$ 表示 $s[1\dots i]$ 通过删去若干字符，最后一个（不完整的） bessie 已经凑齐了前 $k$ 位的最大完整 bessie 数以及对应的最小删除代价。

我们把 最大完整 bessie 数 以及 对应的最小删除代价 的二元组称为一个最优方案。注意因为我们要求的是保证 bessie 数最大的情况下的最小删除代价，所以我们要优先考虑最大化 bessie 数，最小删除代价也是在保证最大的 bessie 数前提下的。

所以可以得出和上面类似的转移方程：

1. 当 $s[i]$ 等于 bessie 中的第 $k$ 个字母时，$f[i][k]=\operatorname{best\ option}(f[i-1][k]+(0,c[i]),f[i-1][k-1])$。
2. 否则，$f[i][k]=f[i-1][k]+(0,c[i])$。
3. 当 $k=0$ 时，$f[i][k]=\operatorname{best\ option}(f[i-1][0],f[i][6]+(1,0))$。

这样状态就变成 $\mathcal O(n)$ 级别的了，总的复杂度 $\mathcal O(n)$。

#include <bits/stdc++.h>
#define pii pair<int,int>
#define il inline
using namespace std;
const int N=2e5+5;
int n,c[N];pii f[N][10];
string s,b=" bessie";
il pii best_option(pii x,pii y)
{
	if(x.first<y.first)return y;
	if(x.first==y.first)
	{
		if(x.second<=y.second)return x;
		return y;
	}
	return x;
}
il pii add(pii x,pii y){return {x.first+y.first,x.second+y.second};}
signed main()
{
	cin>>s;n=s.size();s=' '+s;
	for(int i=1;i<=n;++i)cin>>c[i];
	for(int i=0;i<=n;++i)for(int k=0;k<=6;++k)f[i][k]={-1,1e9};
	f[0][0]={0,0};
	for(int i=1;i<=n;++i)
	{
		for(int k=1;k<=6;++k)
		{
			if(s[i]==b[k])f[i][k]=best_option(add(f[i-1][k],{0,c[i]}),f[i-1][k-1]);
			else f[i][k]=add(f[i-1][k],{0,c[i]});
		}	
		f[i][0]=best_option(f[i-1][0],add(f[i][6],{1,0}));
	}
	cout<<f[n][0].first<<endl<<f[n][0].second;
	return 0;
}