D
e
s
c
r
i
p
t
i
o
n
\mathcal{Description}
D
e
s
c
r
i
p
t
i
o
n
小
D
D
D
正在研究魔法。
小
D
D
D
得到了远古时期的魔法咒语
S
S
S
,这个咒语共有
n
n
n
个音节,每个音节都可以
抽象为一个小写英文字母。
但是很快小
D
D
D
发现这个咒语并不能直接说出——它具有一定的危险性。
小
D
D
D
进行了一些仔细的研究,很快发现危险来源于
m
m
m
个禁忌词
T
1
,
T
2
,
…
,
T
m
T_1 , T_2 , \ldots, T_m
T
1
,
T
2
,
…
,
T
m
。
小
D
D
D
发现,只要说出的咒语中,连续地包含了其中某个禁忌词,那么就会带来很
大的危险。换言之,对于任意
1
≤
i
≤
m
1 ≤ i ≤ m
1
≤
i
≤
m
,
T
i
T_i
T
i
都不能是最终说出的咒语
S
′
S’
S
′
的子串。
于是小
D
D
D
决定在原来的咒语
S
S
S
上做出一定的删减,使得它不再包含任何禁忌词。
小
D
D
D
发现如果他跳过咒语中第
i
i
i
个音节,那么咒语的威力会减少
a
i
a_i
a
i
。
小
D
D
D
想要知道,如何跳过音节可以得到一个安全的咒语,而威力的减少量最少。
值得一提的是,如果小
D
D
D
跳过了某个音节,那么与之相邻两个音节也不会变得连续。
但是小
D
D
D
并不会,请你帮帮他。
S
o
l
u
t
i
o
n
\mathcal{Solution}
S
o
l
u
t
i
o
n
先用所有的
T
T
T
对
S
S
S
做
K
M
P
KMP
K
M
P
，得到若干个区间
那么我们的问题就转化成了有
n
n
n
个点和若干个区间，每个点有点权，你要选若干个点使得每个区间内都至少包含一个点，问最小点权和是多少
考虑
D
P
DP
D
P
先将区间按照
r
r
r
升序排序
设
f
i
,
j
f_{i,j}
f
i
,
j
表示使前
i
i
i
个区间都合法，最后一个点为
j
j
j
的最小点权和是多少
那么对一个区间
[
l
i
,
r
i
]
[l_i,r_i]
[
l
i
,
r
i
]
，其有效的
f
f
f
的区间也为
[
l
i
,
r
i
]
[l_i,r_i]
[
l
i
,
r
i
]
考虑
f
i
,
j
f_{i,j}
f
i
,
j
肯定是由
f
i
−
1
,
k
k
∈
[
l
i
−
1
,
r
i
−
1
]
f_{i-1,k}\ k\in [l_{i-1},r_{i-1}]
f
i
−
1
,
k
k
∈
[
l
i
−
1
,
r
i
−
1
]
转移来的
于是我们可以去掉一维
设
f
i
f_i
f
i
表示最后一个点为
i
i
i
时的答案
然后考虑一个一个的加区间
如图，
后一个区间的蓝色部分的
f
f
f
值与前一个区间应是一样的
而红色区间的值则由绿色区间的值转移过来，设红色区间的一个值为
f
k
f_k
f
k
，则有
f
k
=
min
{
f
j
,
j
∈
[
绿
色
]
}
+
a
k
f_k=\min\{f_j,j\in[绿色]\}+a_k
f
k
=
min
{
f
j
,
j
∈
[
绿
色
]
}
+
a
k
我们可以用线段树查询绿色区间的最小值，并维护红色区间的增值
C
o
d
e
\mathcal{Code}
C
o
d
e
/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年11月11日 星期一 08时24分38秒
*******************************/
#include <cstdio>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200005;
const int maxm = 2000006;
const int inf = 0x7f7f7f7f;
//cin 省掉了快读
int n,m,tot;
int nxt[maxn],l[maxm],r[maxm],w[maxn],id[maxn];
char s[maxn],t[maxn];
bool cmp (int x,int y){ return r[x]^r[y]?r[x]<r[y]:l[x]<l[y];}
//{{{Get
void Get (char *s,int len)
{
int j=1,k=0;
reset(nxt);
while (j<=len){
if (!k||s[j]==s[k]) nxt[++j]=++k;
else k=nxt[k];
}
}
//}}}
//{{{Match
int Match (char *s,char *t)//s appears in t
{
int len=strlen(s+1);
Get(s,len);
int j=1,k=1,ans=0;
while (k<=n){
if (!j||s[j]==t[k]) ++j,++k;
else j=nxt[j];
if (j==len+1){
l[++tot]=k-len,r[tot]=k-1,id[tot]=tot;
j=nxt[j];
}
}
return ans;
}
//}}}
//{{{SegmentTree
namespace SegmentTree
{
#define cl k<<1
#define cr k<<1|1
#define lm (lt[k]+rt[k])/2
#define rm (lt[k]+rt[k])/2+1
const int maxt = 1000006;
int lt[maxt],rt[maxt],val[maxt],lazy[maxt],tag[maxt],sum[maxt];
//{{{build
void build (int l,int r,int k=1)
{
lt[k]=l,rt[k]=r,val[k]=inf;
if (l==r) return void(sum[k]=w[l]);
build(l,lm,cl);
build(rm,r,cr);
sum[k]=min(sum[cl],sum[cr]);
}
//}}}
//{{{pushdownl
void pushdownl (int k)
{
val[cl]=lazy[k]*sum[cl],val[cr]=lazy[k]*sum[cr];
lazy[cl]+=lazy[k],lazy[cr]+=lazy[k];
lazy[k]=0;
}
//}}}
//{{{pushdownt
void pushdownt (int k)
{
tag[cl]+=tag[k],tag[cr]+=tag[k];
val[cl]+=tag[k],val[cr]+=tag[k];
tag[k]=0;
}
//}}}
//{{{modify
void modify (int l,int r,int v,int k=1)
{
if (lt[k]>=l&&rt[k]<=r){
val[k]=sum[k]+v;
++lazy[k],tag[k]+=v;
return;
}
if (lazy[k]) pushdownl(k);
if (tag[k]) pushdownt(k);
if (l<=lm) modify(l,r,v,cl);
if (r>=rm) modify(l,r,v,cr);
val[k]=min(val[cl],val[cr]);
}
//}}}
//{{{query
int query (int l,int r,int k=1)
{
if (lt[k]>=l&&rt[k]<=r) return val[k];
int res=inf;
if (lazy[k]) pushdownl(k);
if (tag[k]) pushdownt(k);
if (l<=lm) res=min(res,query(l,r,cl));
if (r>=rm) res=min(res,query(l,r,cr));
return res;
}
//}}}
}
using namespace SegmentTree;
//}}}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",s+1);
for (int i=1;i<=n;++i) cin>>w[i];
for (int i=1;i<=m;++i){
scanf("%s",t+1);
Match(t,s);
}
sort(id+1,id+tot+1,cmp);
int cnt=0;
for (int i=1;i<=tot;++i){
int cur=id[i];
while (i+1<=tot&&l[id[i+1]]==l[cur]&&r[id[i+1]]==r[cur]) ++i;
id[++cnt]=cur;
}
tot=cnt;
if (!tot) return printf("0\n"),0;
build(1,n);
modify(l[id[1]],r[id[1]],0);
for (int i=2;i<=tot;++i){
int tl=l[id[i-1]],tr=r[id[i-1]];
int lt=l[id[i]],rt=r[id[i]];
int tmp=query(tl,tr);
l[id[i]]=max(lt,tl);
if (lt>tr) modify(lt,rt,tmp);
else if (rt>tr) modify(tr+1,rt,tmp);
}
printf("%d\n",query(l[id[tot]],r[id[tot]]));
return 0;
}
如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧