本文主要是介绍HDU3613 Best Reward - exkmp/Manacher，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3613
题意：多组数据,给定每个字母的价值和一个串S，要把这个串S分成两个串T1、T2，若某串T是回文串那么就能获得该串上字母的价值，否则可获得的价值为0，求最大价值
题解：RT 用exkmp或者马拉车搞一搞就好了
心得什么的：撒比的我想着用exkmp搞，练习一下，结果..一搞就搞了半个世纪qwq至今WA原因不明。于是气愤的我改用Manacher水过了= =
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 510000int len,n,w[maxn],a[maxn],g[maxn*2];
char s[maxn],ss[maxn*2];
int mymin(int x,int y){return (x<y)?x:y;}
int mymax(int x,int y){return (x>y)?x:y;}
void init()
{int i;len=0;for (i=1;i<=26;i++) scanf("%d",&a[i]);scanf("\n");gets(s+1);n=strlen(s+1);w[0]=0;for (i=1;i<=n;i++) w[i]=w[i-1]+a[s[i]-'a'+1];ss[len]='|';for (i=1;i<=n;i++){ss[++len]=s[i];ss[++len]='|';}
}
void Manacher()
{int i,mx=0,p=0;memset(g,0,sizeof(g));g[0]=1;for (i=1;i<=len;i++){if (i<mx) g[i]=mymin(g[p*2-i],mx-i);else g[i]=1;while (i+g[i]<=len && ss[i+g[i]]==ss[i-g[i]]) g[i]++;if (i+g[i]>mx) mx=i+g[i],p=i;}
}
void ges()
{int i,ans=0,sum;for (i=1;i<n;i++){sum=0;if (g[i]-1==i) sum+=w[i];//前i个是回文int xx=i+n;if (n-i==g[xx]-1) sum+=w[n]-w[i];//后n-i+1个是回文ans=mymax(ans,sum);}printf("%d\n",ans);
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int T;scanf("%d",&T);while (T--){init();Manacher();ges();}return 0;
}还有WA的exkmp的代码，，，ORZ有没有好心的大大帮我看看那里有问题【我的做法挺蠢的qwq
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 510000int n,w[maxn],a[30];
int ex[3][maxn],nt[3][maxn];
char s[3][maxn];
int mymax(int x,int y){return (x>y)?x:y;}
int mymin(int x,int y){return (x<y)?x:y;}
void exkmp(int l1,int l2,int tp)
{int id,mx,i;memset(nt[tp],0,sizeof(nt[tp]));id=1;mx=0;nt[tp][1]=n;for (i=2;i<=n;i++){if (i+nt[tp][i-id+1]-1<mx) nt[tp][i]=nt[tp][i-id+1];else{nt[tp][i]=mymax(0,mx-i+1);while (i+nt[tp][i]<=n && s[l1][i+nt[tp][i]]==s[l1][1+nt[tp][i]]) nt[tp][i]++;if (i+nt[tp][i]-1>mx) mx=i+nt[tp][i]-1,id=i;}}memset(ex[tp],0,sizeof(ex[tp]));id=0;mx=0;for (i=1;i<=n;i++){if (i+nt[tp][i-id+1]-1<mx) ex[tp][i]=nt[tp][i-id+1];else{ex[tp][i]=mymax(0,mx-i+1);while (i+ex[tp][i]<=n && s[l1][1+ex[tp][i]]==s[l2][i+ex[tp][i]]) ex[tp][i]++;if (i+ex[tp][i]-1>mx) mx=i+ex[tp][i]-1,id=i;}}
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);int T,i,ans,sum,dz;scanf("%d",&T);while (T--){for (i=1;i<=26;i++) scanf("%d",&a[i]);scanf("\n");gets(s[1]+1);n=strlen(s[1]+1);w[0]=0;for (i=1;i<=n;i++) s[2][n-i+1]=s[1][i];for (i=1;i<=n;i++) w[i]=w[i-1]+a[s[1][i]-'a'+1];exkmp(1,2,1);exkmp(2,1,2);ans=0;if (n==2) ans=w[n];for (i=2;i<n;i++){sum=0;if (ex[1][n-i+1]==i) sum+=w[i];//表示前i个字符是回文串if (ex[2][i+1]==n-i) sum+=w[n]-w[i];//表示后n-i个字符是回文串ans=mymax(ans,sum);}printf("%d\n",ans);}return 0;
}这篇关于HDU3613 Best Reward - exkmp/Manacher的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
