本文主要是介绍HDU 3613 Best Reward 正反两次扩展KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：HDU 3613 Best Reward
题意：每个字母对应一个权值 将给你的字符串分成两部分 如果一部分是回文 这部分的值就是每个字母的权值之和 求一种分法使得2部分的和最大
思路：考虑扩展KMP 输出a串 得到a的反串b 求出f[0]和f[1] 和 extend[0]和extend[1] 正反求2次
枚举位置i 分成2部分0到i-1 和i到n-1 因为分成的2部分必须组成原字符串 就是不能多也不能少
那么判断i+extend[i]是否等于n 等于说明i到n-1这个部分是回文串 sum1 为这部分的值 如果这部分不是回文sum1 = 0
判断0到i-1是不是回文 将a和b翻转 那么就和判断i到n-1是一样的 所以上面正反求了2次 sum2 为这部分的值 如果这部分不是回文sum2 = 0
去sum1+sum2的最大值 另外字符串的值可以递推求得
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500010;
int f[2][maxn], ex[2][maxn];
char a[maxn], b[maxn];
int id[26], dp[2][maxn];
void getFail(char* s, int id, int n)
{int k = 1, p = 0;while(p+1 < n && s[p] == s[p+1])p++;f[id][0] = n;f[id][1] = p;for(int i = 2; i < n; i++){int l = f[id][i-k];int p = f[id][k]+k-1;if(i+l-1 < p)f[id][i] = l;else{int j = p-i+1;if(j < 0)j = 0;while(i+j < n && s[i+j] == s[j])j++;f[id][i] = j;k = i;}}
}void getEx(char* s, char* t, int id, int n)
{int k = 0, p = 0;while(p < n && s[p] == t[p])p++;ex[id][0] = p;for(int i = 1; i < n; i++){int l = f[id^1][i-k];int p = ex[id][k]+k-1;if(i+l-1 < p)ex[id][i] = l;else{int j = p-i+1;if(j < 0)j = 0;while(i+j < n && s[i+j] == t[j])j++;ex[id][i] = j;k = i;}}
}int main()
{int T;scanf("%d", &T);while(T--){for(int i = 0; i < 26; i++)scanf("%d", &id[i]);scanf("%s", a); int n = strlen(a);for(int i = 0; i < n; i++){b[i] = a[n-i-1];if(i)dp[0][i] = id[a[i]-'a'] + dp[0][i-1];elsedp[0][i] = id[a[i]-'a'];}for(int i = 0; i < n; i++){if(i)dp[1][i] = dp[1][i-1] + id[b[i]-'a'];elsedp[1][i] = id[b[i]-'a'];}getFail(a, 0, n);getFail(b, 1, n);getEx(a, b, 0, n); getEx(b, a, 1, n);int ans = 0;for(int i = 1; i < n; i++){int sum1 = 0, sum2 = 0;if(i+ex[0][i] == n)sum1 = dp[1][ex[0][i]-1];int j = n-i;if(j+ex[1][j] == n)sum2 = dp[0][ex[1][j]-1];ans = max(ans, sum1+sum2);//printf("%d %d\n", ex[0][i], ex[1][i]);}printf("%d\n", ans);}return 0;
}
这篇关于HDU 3613 Best Reward 正反两次扩展KMP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
