长乐 Day 11

Today学习单调和状压

e

没什么评价

开始贴代码

我爱写博客

#include<bits/stdc++.h>
using namespace std;
const int L=2e5+10;
int n,m;
int a[L];
char s[L];
char ch[20][L];
int pre[L],nxt[L];
int dp[L];
int l=1,r=0;
int q[L];
void pret(int x)
{
    int lc=strlen(ch[x]+1);
    int j=0;
    for(int i=1;i<lc;i++)
    {
        while(j&&ch[x][j+1]!=ch[x][i+1])
            j=nxt[j];
        if(ch[x][i+1]==ch[x][j+1])
            j++;
        nxt[i+1]=j;
    }
}
void kmp(int x)
{
    int ls=strlen(s+1);
    int lc=strlen(ch[x]+1);
    int j=0;
    for(int i=0;i<ls;i++)
    {
        pre[i+1]=max(pre[i+1],pre[i]);
        while(j&&ch[x][j+1]!=s[i+1])
            j=nxt[j];
        if(ch[x][j+1]==s[i+1])
            j++;
        if(j==lc)
        {
            pre[i+1]=max(pre[i+1],i+1-lc+1);
            j=nxt[j];
        }
    }
}
signed main(void)
{
    scanf("%d%d%s",&n,&m,s+1);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch[i]+1);
        pret(i);
        kmp(i);
    }
    n++;
    for(int i=0;i<=n;i++)
    {
        while(l<=r&&q[l]<pre[i-1])
            l++;
        dp[i]=dp[q[l]]+a[i];
        while(l<=r&&dp[q[r]]>=dp[i])
            r--;
        r++;
        q[r]=i;
    }
    printf("%d",dp[n]);
    return 0;
}