题目
描述
题目大意
给你一堆小串，每个小串都有一定的分数。
让你构造一个字符串，若子串中出现了之前的小串，就可以得到对应的分数（可以重复）
问最大分数。
思考历程
一看这题就知道是什么字符串方面的算法。
然后就很自然地想到AC自动机，多串匹配嘛！
接下来就想到建字符串的过程中，一个指针在AC自动机上跳来跳去……
先建出AC自动机，然后算出到达每个节点的贡献。
对于每个节点，枚举字母，若没有出边，就想着用往上跳，然后将出边连向那个地方。
从此AC自动机变成了一张有向图，每个点都有条出边。题目就转成了在这张有向图上，走步所的最大点权和。
感觉转化到这一步之后就想不出什么了，考虑过最长路一类的做法，都是没有成功。
于是我也不追求满分了，直接跑DP水分。
正解
事实上……
题目中有这么一句话：字符串的长度和不超过。
知道这一切之后我疯了。
既然这样，那不就是一个裸的矩阵乘法吗？
时间就是，在6000ms中肯定是可以过的。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
int n;
long long m;
int a[210];
char str[210];
struct Node{
int c[26],fail;
int v;
} d[210];
int cnt,root;
inline void insert(char *s,int val){
int t=root;
for (;*s;++s){
if (!d[t].c[*s-'a'])
d[t].c[*s-'a']=++cnt;
t=d[t].c[*s-'a'];
}
d[t].v+=val;
}
inline void build(){//求fail，顺便做了对空儿子的处理。显然这两步是可以放在一起的
static int q[210];
int head=0,tail=1;
d[root].fail=root;
q[1]=root;
do{
int t=q[++head];
for (int i=0;i<26;++i){
if (d[t].c[i])
q[++tail]=d[t].c[i];
if (t==root){
if (d[t].c[i])
d[d[t].c[i]].fail=root;
else
d[t].c[i]=root;
continue;
}
int nxt=d[t].fail;
while (nxt!=root && !d[nxt].c[i])
nxt=d[nxt].fail;
if (d[nxt].c[i]){
if (d[t].c[i]){
d[d[t].c[i]].fail=d[nxt].c[i];
d[d[t].c[i]].v+=d[d[nxt].c[i]].v;
}
else
d[t].c[i]=d[nxt].c[i];
}
else{
if (d[t].c[i])
d[d[t].c[i]].fail=root;
else
d[t].c[i]=root;
}
}
}
while (head!=tail);
}
struct Matrix{
long long mat[210][210];
inline void operator*=(Matrix &b){
static Matrix res;
memset(res.mat,200,sizeof res);
for (int i=1;i<=cnt;++i)
for (int j=1;j<=cnt;++j)
for (int k=1;k<=cnt;++k)
res.mat[i][j]=max(res.mat[i][j],mat[i][k]+b.mat[k][j]);
memcpy(mat,res.mat,sizeof mat);
}
} f;
inline void get_pow(Matrix &x,long long m){
static Matrix res;
memset(res.mat,200,sizeof res);
for (int i=1;i<=cnt;++i)
res.mat[i][i]=0;
for (;m;m>>=1,x*=x)
if (m&1)
res*=x;
memcpy(x.mat,res.mat,sizeof x);
}
int main(){
cnt=root=1;
scanf("%d%lld",&n,&m);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (int i=1;i<=n;++i){
scanf("%s",str);
insert(str,a[i]);
}
build();
memset(f.mat,200,sizeof f);
for (int i=1;i<=cnt;++i)
for (int j=0;j<26;++j)
f.mat[i][d[i].c[j]]=d[d[i].c[j]].v;
get_pow(f,m);
long long ans=0;
for (int i=1;i<=cnt;++i)
ans=max(ans,f.mat[1][i]);
printf("%lld
",ans);
return 0;
}
总结
不想说什么……
如果不是没有看到，我这题早就AC的……