?Best Reward

Problem's Link: ??http://acm.hdu.edu.cn/showproblem.php?pid=3613

---

?

Mean:?

給你一個字符串，每個字符都有一個權(quán)值(可能為負)，你需要將這個字符串分成兩個子串，使得這兩個子串的價值之和最大。一個子串價值的計算方法：如果這個子串是回文串，那么價值就是這個子串所有字符權(quán)值之和；否則價值為0。

?

analyse:

?

擴展KMP算法運用。
總體思路：
找出所有包含第一個字母的回文串和包含最后一個字母的回文串，然后O(n)掃一遍，每次判斷第i個字母之前（包含第i個字母）的子串是否是回文，以及從第i個字母后的子串是否是回文，然后計算出答案，取最大值。
具體做法：
假設(shè)輸入的字符串是"abcda"
構(gòu)造串s1="abcda#adcba"
求s1的Next數(shù)組，得到了包含第一個字母的回文串的位置；
構(gòu)造串s2="adcba#abcda"
求s2的Next數(shù)組，得到了包含最后一個字母的回文串的位置；
用兩個flag數(shù)組標(biāo)記這些位置，然后掃一遍就得答案了。
中間加一個'#'并后接反串的目的是：當(dāng)整個串都是回文的時候能夠被Next數(shù)組記錄下。

?

?

Time complexity: O(nlogn)

?

Source code:?

?第一遍寫，不夠優(yōu)化：

/* * this code is made by crazyacking * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <string> #include <stack> #include <cmath> #include <set> #include <map> #include <cstdlib> #include <climits> #include <vector> #include <iostream> #include <algorithm> #include <cstring> #define MAXN 500010*2 #define LL long long using namespace std; int len; int Next[MAXN],ne[MAXN]; int sum[MAXN]; vector<int> val; bool flag1[MAXN],flag2[MAXN]; char s[MAXN],s1[MAXN],s2[MAXN],sr[MAXN]; void get_sum() {sum[0]=val[s[0]-'a'];for(int i=1;i<len;++i)sum[i]=sum[i-1]+val[s[i]-'a']; } void get_s1() {strcpy(s1,s);s1[len]='#';s1[len+1]='\0';strcat(s1,sr); } void get_s2() {strcpy(s2,sr);s2[len]='#';s2[len+1]='\0';strcat(s2,s); }void get_Next(char s[]) {Next[0]=0;int s_len=strlen(s);for(int i=1,k=0;i<s_len;++i){while(k!=0 && s[i]!=s[k])k=Next[k-1];if(s[i]==s[k]) k++;Next[i]=k;} } int main() {ios_base::sync_with_stdio(false);cin.tie(0);int Cas;cin>>Cas;while(Cas--){val.clear();int cnt=26,t;while(cnt--){cin>>t,val.push_back(t);}scanf("%s",s);len=strlen(s);if(strlen(s)==1){printf("%d\n",val[s[0]-'a']);continue;}get_sum();strcpy(sr,s);strrev(sr);get_s1();get_s2();memset(flag1,0,sizeof flag1);memset(flag2,0,sizeof flag2);get_Next(s1);int k=Next[2*len];while(k!=0){flag1[k-1]=1;k=Next[k-1];}get_Next(s2);k=Next[2*len];while(k!=0){flag2[k-1]=1;k=Next[k-1];}reverse(flag2,flag2+len);long long ans=INT_MIN;long long tmp=0;for(int i=0;i<len-1;++i){tmp=0;if(flag1[i]){tmp+=sum[i];}if(flag2[i+1]){tmp=tmp+(sum[len-1]-sum[i]);}if(tmp>ans)ans=tmp;}cout<<ans<<endl;}return 0; } /**/ View Code

?

優(yōu)化后的代碼：

?

/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-07-16.26 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; const int MAXN=500010; int val[30],Next[MAXN*2],sum[MAXN]; char s[MAXN],s1[MAXN*2]; bool flag[2][MAXN]; void get_sum() {int len=strlen(s);sum[0]=val[s[0]-'a'];for(int i=1;i<len;++i)sum[i]=sum[i-1]+val[s[i]-'a']; }void get_Next(char ss[]) {int len=strlen(ss);Next[0]=0;int k=0;for(int i=1;i<len;++i){while(k!=0 && ss[i]!=ss[k])k=Next[k-1];if(ss[i]==ss[k]) k++;Next[i]=k;} }void get_flag(int x) {strcpy(s1,s);int len=strlen(s);s1[len]='#';strrev(s);strcat(s1+len+1,s);get_Next(s1);len=strlen(s1);int k=Next[len-1];while(k!=0){flag[x][k-1]=1;k=Next[k-1];}memset(s1,0,sizeof s1); } int main() {ios_base::sync_with_stdio(false);cin.tie(0);int Cas;scanf("%d",&Cas);while(Cas--){for(int i=0;i<26;++i)scanf("%d",&val[i]);scanf("%s",s);if(strlen(s)==1){printf("%d\n",val[s[0]-'a']);continue;}get_sum();memset(flag,0,sizeof flag);get_flag(0);get_flag(1);int len=strlen(s);reverse(flag[1],flag[1]+len);long long ans=LLONG_MIN,tmp;for(int i=0;i<len-1;++i){tmp=0;tmp=(flag[0][i]?sum[i]:0)+(flag[1][i+1]?sum[len-1]-sum[i]:0);ans=ans>tmp?ans:tmp;}printf("%lld\n",ans);}return 0; } /**/ View Code

?

總結(jié)

以上是生活随笔為你收集整理的扩展KMP --- HDU 3613 Best Reward的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。