题意
小泽发了一篇博客，由 n 个小写英文字母组成，由于包含违禁词，被自动隐藏。
具体地，违禁词有 m 个，分别为 T1,T2,…,Tm 。
小泽发现，只要博客中，连续地包含了其中违禁词，那么博客就会被自动隐藏。换言之，对于任意 1≤i≤m ， Ti 都不能是最终发表的博客 S 的子串。
于是小泽决定在原来的博客 S 上把一部分字母替换成空格，使得它不再包含违禁词。如果她把第 i 个字母替换成空格，与之相邻的两个字母将不会连续，但是整篇博客的价值会减少 ai 。
小泽想要知道，如何替换可以得到一篇不会被自动隐藏的博客，而价值的减少量最少。请你帮她回答这个问题。
1≤n=|S|≤2×105 ， 1≤m≤10 ， 1≤|Ti|≤2×105 ， 0≤ai≤1000.
题解
综合性强的一道好题。
根据数据范围可知 dp 数组应该只有一维状态，那么只能设 \(dp_i\) 表示处理好前 \(i\) 的字母减少的最小价值，而且第 \(i\) 个位置必须改为空格。
可以想到先预处理出违禁串在原串出现的位置，这个可以用 KMP 解决。
把每一个违禁串的位置记为 \([l,r]\)，记录 \(pre_r=l\).
那么对于每一个 \(dp_i\)，有 \(dp_i\)=\(dp_j\)+\(a_i\).
考虑 \(j\) 的取值范围，是要将 \(i-1\) 之前的位置处理好，那么最后一个需要覆盖的区间就是 \([pre_{i-1},i-1]\)。
\(pre_i\) 虽然实际意义上不一定单调不降，但是实际上要维护单调不降，才能转移 dp，同时也能进行单调队列优化。
初始的时候队列里要加入一个“0”元素，保证从“0”转移的情况。
代码
#include
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 2e5+10;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n,m,nxt[N],pre[N];
char s[N],c[11][N];
int a[N];
int dp[N],q[N],l=1,r;
void pretreat(int op)
{
int j=0,len=strlen(c[op]+1);
for(int i=1;i { while(j&&c[op][j+1]!=c[op][i+1]) j=nxt[j]; if(c[op][j+1]==c[op][i+1]) j++; nxt[i+1]=j; } } void kmp(int op) { int j=0,len=strlen(s+1),lenc=strlen(c[op]+1); for(int i=0;i { pre[i+1]=max(pre[i],pre[i+1]); while(j&&c[op][j+1]!=s[i+1]) j=nxt[j]; if(c[op][j+1]==s[i+1]) j++; if(j==lenc) pre[i+1]=max(pre[i+1],i+1-lenc+1),j=nxt[j]; //我吐了，lenc打成len...调了好久 //注意细节,pre[i+1]的位置刚好是一个违规词 } } int main() { n=read(),m=read(); scanf("%s",s+1); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++) { scanf("%s",c[i]+1); pretreat(i); kmp(i); } n++; l=1,r=0; for(int i=0;i<=n;i++) { while(l<=r&&q[l] dp[i]=dp[q[l]]+a[i]; while(l<=r&&dp[q[r]]>=dp[i]) r--; q[++r]=i; } printf("%d",dp[n]); return 0; }