【题解】P9190 [USACO23OPEN] Pareidolia G

· · 题解

设字符串的长度为 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;
}