题目大概说给几个字符串，每个字符串都有一个开心值，一个串如果包含一次这些字符串就加上对应的开心值，问长度n的串开心值最多可以是多少。
POJ2778。。复习下。。太弱了都快不会做了。。
这个矩阵的乘法定义是不同的，m[i][j]=max(m1[i][k]+m2[k][j])，即从i走到k能获得的最大值与从k走到j能获得的最大值之和去更新从i到j能获得的最大值。
另外。。关于矩阵内的初始值。。用-1表示从i不能到j，比如初始的时候，i不能走一步到j结点这时值就应该设置成-1；而不能用0，因为0是有意义的，它表示能走但不能获得价值。。这个搞了好久。。好累。。
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std; int tn,ch[][],fail[],sum[];
void insert(char *s,int a){
int x=;
for(int i=; s[i]; ++i){
int y=s[i]-'a';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
}
sum[x]+=a;
}
void getfail(){
queue<int> que;
for(int i=; i<; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int x=que.front(); que.pop();
for(int y=; y<; ++y){
if(ch[x][y]) que.push(ch[x][y]),fail[ch[x][y]]=ch[fail[x]][y],sum[ch[x][y]]+=sum[ch[fail[x]][y]];
else ch[x][y]=ch[fail[x]][y];
}
}
} int val[];
char str[]; struct Mat{
long long m[][];
Mat(){
memset(m,-,sizeof(m));
}
};
Mat operator*(const Mat &m1,const Mat &m2){
Mat m;
for(int i=; i<=tn; ++i){
for(int j=; j<=tn; ++j){
for(int k=; k<=tn; ++k){
if(m1.m[i][k]==- || m2.m[k][j]==-) continue;
m.m[i][j]=max(m.m[i][j],m1.m[i][k]+m2.m[k][j]);
}
}
}
return m;
} int main(){
int n; long long l;
scanf("%d%lld",&n,&l);
for(int i=; i<=n; ++i) scanf("%d",val+i);
for(int i=; i<=n; ++i){
scanf("%s",str);
insert(str,val[i]);
} getfail(); Mat m;
for(int i=; i<=tn; ++i){
for(int j=; j<; ++j){
m.m[i][ch[i][j]]=sum[ch[i][j]];
}
} Mat res=m;
--l;
while(l){
if(l&){
res=res*m;
}
m=m*m;
l>>=;
} long long ans=;
for(int i=; i<=tn; ++i){
ans=max(ans,res.m[][i]);
}
printf("%lld",ans);
return ;
}