题解：P9190 [USACO23OPEN] Pareidolia G

TP2010 · 2026-11-09 21:43:29 · 题解

首先第一问可以贪心解决，从前往后能匹配尽量匹配。

考虑一个暴力的DP。

记 f(i,j,k) 表示考虑了前缀 i，当前已经匹配到了第 j 个串的第 k 个字符。不过为了方便，我们合并成 f(i,j')，其中 j'=6j+k。

然后转移有几种：

1. 考虑从 i 开始构造这个连续子串，前面 [1,i] 都不算了。f(i,0)=0。

2. 考虑匹配一个字符，如果可以匹配。f(i,j'+1)\gets f(i-1,j')

3. 考虑截断。f(i,j,0)\gets f(i-1,j,k)。

   截断操作的作用其实是使得连续子串中间允许其它字符出现。

4. 考虑删除。f(i,j')\gets f(i-1,j')。

状态数是 O(n^2) 的？确实是这个样子，但是可以优化。

对于每个前缀 i，要使得最后能够到达最大次数，它的 j 的种数是 O(1) 的！因为如果 j,k 可以，那么 (j-1,k) 就一定会被淘汰，我们只会保留同一个 k 里面地最大的 j。

我们可以考虑对每个后缀倒着贪心一遍，这样可以求出一个对应的最大匹配长度 len，然后再和我们 DP 时的 j' 拼起来，如果发现拼起来的长度 \ge 6\op{ans1}，最后我们直接可以这样用这个方案达到最大，所以合法。

然后记 g(i) 表示 [i+1,|S|] 的后缀的反过来的最大匹配长度。

那么，j' 范围就是 [6\op{ans1}-g(i),6(\op{ans1}+1)-1-g(i)]。

于是状态数变为 6n，复杂度为 O(n)。

:::info[Code]

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=200005;
namespace Fastio{
    #define SIZIO (1<<22)
    #define gc() (rp1==rp2&&(rp2=(rp1=buf)+fread(buf,1,SIZIO,stdin))==rp1?EOF:*rp1++)
    char buf[SIZIO+1],*rp1,*rp2;
    inline int read(){
        int d=0,f=0;char ch=gc();
        while (!isdigit(ch)) f|=(ch=='-'),ch=gc();
        while (isdigit(ch)) d=(d<<1)+(d<<3)+ch-'0',ch=gc();
        return f?-d:d;
    }
    inline void read(char &c){c=gc();while(c<33||c>126) c=gc();}
    inline void read(char *s){
        char ch=gc();
        while(ch<33||ch>126)ch=gc();
        while(ch>=33&&ch<=126) (*s++)=ch,ch=gc();
        *s=0;
    }
};using namespace Fastio;

char s[]={'b','e','s','s','i','e'},S[N];
int f[N][7],n,a[N],g[N],l[N];
inline void cmin(int &x,int y){(x>y)&&(x=y);}
bool is(int i,int j){return j-l[i]>=0&&j-l[i]<=5;}
signed main(){
    read(S+1),n=strlen(S+1);
    for (int i=1;i<=n;i++) a[i]=read();
    g[n]=0;
    for (int i=n,j=5,k=0;i>=1;i--){
        if (S[i]==s[j]) j--,k++;
        g[i-1]=k;if (j==-1) j=5;
    }
    int tot=g[0]/6,ans=1e9;l[0]=6*tot-g[0];
    for (int i=0;i<=n;i++)
        for (int j=0;j<=6;j++) f[i][j]=1e9;
    if (is(0,0)) f[0][0-l[0]]=0;
    for (int i=1;i<=n;i++){
        l[i]=6*tot-g[i];
        if (is(i,0)) f[i][0-l[i]]=0;
        for (int j=max(6*tot-g[i-1],0),up=6*(tot+1)-g[i-1]-1;j<=up;j++){
            if (is(i,j)) cmin(f[i][j-l[i]],f[i-1][j-l[i-1]]+a[i]);
            if (is(i,j/6*6)) cmin(f[i][j/6*6-l[i]],f[i-1][j-l[i-1]]);
            if (is(i,j+1)&&S[i]==s[j%6]) cmin(f[i][j-l[i]+1],f[i-1][j-l[i-1]]);
        }
        if (is(i,tot*6)) ans=min(ans,f[i][6*tot-l[i]]);
    }
    printf("%d\n%d\n",tot,ans);
    return 0;
}

:::