Best Reward HDU

Best Reward

题意：每个小写字母对应有一个价值，给一个小写字母组成的串s，现在要把s切割成两段，如果切割后的串是回文串，那么价值就是该段所有字母的价值之和，问总价值最大多少。

将s串反转得到t，分别进行一次扩展KMP，目的是为了判断是否是回文串。

如果s[i]到s[lens-1]是回文串，那么i+ex[i]==len。

枚举切割点更新最大之即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=500010;
 4 char s[maxn],t[maxn];
 5 int exs[maxn],ext[maxn];
 6 int lens,lent;
 7 int nex[maxn];
 8 
 9 int sum[maxn];
10 int v[28];
11 
12 void getnex(char* t){
13     nex[0]=lens;
14     int a=0,p=0;
15     for(int i=1;i<lens;i++){
16         if(i>=p||i+nex[i-a]>=p){
17             if(i>=p) p=i;
18             while(p<lens&&t[p]==t[p-i]) p++;
19             nex[i]=p-i;
20             a=i;
21         }else nex[i]=nex[i-a];
22     }
23 }
24 void exkmp(char* s, char* t, int* ex){
25     getnex(t);
26     int a=0,p=0;
27     for(int i=0;i<lens;i++){
28         if(i>=p||i+nex[i-a]>=p){
29             if(i>=p) p=i;
30             while(p<lens&&p-i<lens&&s[p]==t[p-i]) p++;
31             ex[i]=p-i;
32             a=i;
33         }else ex[i]=nex[i-a];
34     }
35 }
36 
37 int main(){
38     int T;
39     scanf("%d",&T);
40     while(T--){
41         for(int i=0;i<26;i++) scanf("%d",&v[i]);
42         scanf("%s",s);
43         lens=strlen(s);
44         sum[0]=v[s[0]-'a'];
45         t[0]=s[lens-1];
46         for(int i=1;i<lens;i++){
47             sum[i]=sum[i-1]+v[s[i]-'a'];
48             t[i]=s[lens-i-1];
49         }
50         exkmp(s,t,exs);
51         exkmp(t,s,ext);
52         int ans=0;
53         for(int i=1;i<lens;i++){  //枚举切点，在s[i-1]和s[i]之间切割
54             int temp=0;
55             if(i+exs[i]==lens) temp+=sum[lens-1]-sum[i-1];   //s[i]--s[lens]是回文串
56             if(lens-i+ext[lens-i]==lens) temp+=sum[i-1];    //s[0]--s[i-1]是回文串
57             ans=max(ans,temp);
58         }
59         printf("%d
",ans);
60     }
61     return 0;
62 }

View Code

另解：manacher