题目大概说给几个字符串，每个字符串都有一个开心值，一个串如果包含一次这些字符串就加上对应的开心值，问长度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是有意义的，它表示能走但不能获得价值。。这个搞了好久。。好累。。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 8 int tn,ch[222][26],fail[222],sum[222]; 9 void insert(char *s,int a){ 10 int x=0; 11 for(int i=0; s[i]; ++i){ 12 int y=s[i]-'a'; 13 if(ch[x][y]==0) ch[x][y]=++tn; 14 x=ch[x][y]; 15 } 16 sum[x]+=a; 17 } 18 void getfail(){ 19 queue<int> que; 20 for(int i=0; i<26; ++i){ 21 if(ch[0][i]) que.push(ch[0][i]); 22 } 23 while(!que.empty()){ 24 int x=que.front(); que.pop(); 25 for(int y=0; y<26; ++y){ 26 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]]; 27 else ch[x][y]=ch[fail[x]][y]; 28 } 29 } 30 } 31 32 int val[222]; 33 char str[222]; 34 35 struct Mat{ 36 long long m[222][222]; 37 Mat(){ 38 memset(m,-1,sizeof(m)); 39 } 40 }; 41 Mat operator*(const Mat &m1,const Mat &m2){ 42 Mat m; 43 for(int i=0; i<=tn; ++i){ 44 for(int j=0; j<=tn; ++j){ 45 for(int k=0; k<=tn; ++k){ 46 if(m1.m[i][k]==-1 || m2.m[k][j]==-1) continue; 47 m.m[i][j]=max(m.m[i][j],m1.m[i][k]+m2.m[k][j]); 48 } 49 } 50 } 51 return m; 52 } 53 54 int main(){ 55 int n; long long l; 56 scanf("%d%lld",&n,&l); 57 for(int i=1; i<=n; ++i) scanf("%d",val+i); 58 for(int i=1; i<=n; ++i){ 59 scanf("%s",str); 60 insert(str,val[i]); 61 } 62 63 getfail(); 64 65 Mat m; 66 for(int i=0; i<=tn; ++i){ 67 for(int j=0; j<26; ++j){ 68 m.m[i][ch[i][j]]=sum[ch[i][j]]; 69 } 70 } 71 72 Mat res=m; 73 --l; 74 while(l){ 75 if(l&1){ 76 res=res*m; 77 } 78 m=m*m; 79 l>>=1; 80 } 81 82 long long ans=0; 83 for(int i=0; i<=tn; ++i){ 84 ans=max(ans,res.m[0][i]); 85 } 86 printf("%lld",ans); 87 return 0; 88 }