首页 > 代码库 > hdu3613Best Reward
hdu3613Best Reward
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3613
方法较多,扩展KMP还不会-_-||
先放上代码,以后再看。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 const int maxn=500050; 6 int v[28]; 7 int len; 8 int sum[maxn]; 9 int nex[maxn],ext1[maxn],ext2[maxn]; 10 char s[maxn],t[maxn]; 11 void KMP_(char *s,char *t,int *ext) 12 { 13 int j=0,k=1; 14 nex[0]=len; 15 while(j+1<len&&t[j]==t[j+1]) j++; 16 nex[1]=j; 17 for(int i=2;i<len;i++) 18 { 19 int n=k+nex[k]-1,l=nex[i-k]; 20 if(l<n-i+1) nex[i]=l; 21 else { 22 j=max(0,len-i+1); 23 while(i+j<len&&t[i+j]==t[j]) j++; 24 nex[i]=j; 25 k=i; 26 } 27 } 28 j=0; 29 while(j<len&&s[j]==t[j]) j++; 30 ext[0]=j; 31 k=1; 32 for(int i=1;i<len;i++) 33 { 34 int n=k+ext[k]-1,l=nex[i-k]; 35 if(l<n-i+1) ext[i]=l; 36 else { 37 j=max(0,n-i+1); 38 while(i+j<len&&s[i+j]==t[j]) j++; 39 ext[i]=j; 40 k=i; 41 } 42 } 43 44 } 45 int main() 46 { 47 int r; 48 scanf("%d",&r); 49 while(r--) 50 { 51 memset(sum,0,sizeof(sum)); 52 for(int i=0;i<26;i++){ 53 scanf("%d",&v[i]); 54 } 55 scanf("%s",s); 56 len=strlen(s); 57 sum[0]=v[s[0]-‘a‘]; 58 t[len-1]=s[0]; 59 for(int i=1;i<len;i++){ 60 sum[i]=sum[i-1]+v[s[i]-‘a‘]; 61 t[len-i-1]=s[i]; 62 } 63 t[len]=‘\0‘; 64 KMP_(t,s,ext1); 65 KMP_(s,t,ext2); 66 int maxx=-1e-8; 67 for(int i=1;i<len;i++) 68 { 69 int sc=0; 70 if(ext1[len-i]+len-i==len) sc+=sum[i-1]; 71 if(ext2[i]+i==len) sc+=sum[len-1]-sum[i-1]; 72 maxx=max(maxx,sc); 73 } 74 printf("%d\n",maxx); 75 } 76 return 0; 77 78 }
也可以用manacher解决,相对好理解很多,忘记在哪看的了。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip> 10 #define INF 99999999 11 using namespace std; 12 13 const int MAX=500000+10; 14 char s[MAX*2]; 15 int p[MAX*2],sum[MAX],val[27];//sum为前i个字符价值和 16 int per[MAX],pos[MAX];//per标记前i个字符为回文串,pos标记后i个字符为回文串 17 18 int main(){ 19 int n; 20 cin>>n; 21 while(n--){ 22 for(int i=0;i<26;++i)scanf("%d",&val[i]); 23 scanf("%s",s); 24 int len=strlen(s),id=0,ans=-INF,temp=0; 25 for(int i=1;i<=len;++i)sum[i]=sum[i-1]+val[s[i-1]-‘a‘]; 26 for(int i=len;i>=0;--i){ 27 s[i+i+2]=s[i]; 28 s[i+i+1]=‘#‘; 29 } 30 s[0]=‘*‘; 31 for(int i=2;i<len+len+1;++i){ 32 if(p[id]+id>i)p[i]=min(p[2*id-i],p[id]+id-i); 33 else p[i]=1; 34 while(s[i-p[i]] == s[i+p[i]])++p[i]; 35 if(id+p[id]<i+p[i])id=i; 36 if(i-p[i] == 0)per[p[i]-1]=n+1;//表示前缀(前p[i]-1个字符)是回文串 37 if(i+p[i] == len+len+2)pos[p[i]-1]=n+1;//表示后缀(后p[i]-1个字符)是回文串 38 } 39 for(int i=1;i<len;++i){ 40 if(per[i] == n+1)temp+=sum[i]; 41 if(pos[len-i] == n+1)temp+=sum[len]-sum[i]; 42 if(temp>ans)ans=temp; 43 temp=0; 44 } 45 cout<<ans<<endl; 46 } 47 return 0; 48 }
hdu3613Best Reward
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。