Best Reward
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=3613
Mean:
给你一个字符串,每个字符都有一个权值(可能为负),你需要将这个字符串分成两个子串,使得这两个子串的价值之和最大。一个子串价值的计算方法:如果这个子串是回文串,那么价值就是这个子串所有字符权值之和;否则价值为0。
analyse:
扩展KMP算法运用。
总体思路:
找出所有包含第一个字母的回文串和包含最后一个字母的回文串,然后O(n)扫一遍,每次判断第i个字母之前(包含第i个字母)的子串是否是回文,以及从第i个字母后的子串是否是回文,然后计算出答案,取最大值。
具体做法:
假设输入的字符串是"abcda"
构造串s1="abcda#adcba"
求s1的Next数组,得到了包含第一个字母的回文串的位置;
构造串s2="adcba#abcda"
求s2的Next数组,得到了包含最后一个字母的回文串的位置;
用两个flag数组标记这些位置,然后扫一遍就得答案了。
中间加一个'#'并后接反串的目的是:当整个串都是回文的时候能够被Next数组记录下。
Time complexity: O(nlogn)
Source code:
第一遍写,不够优化:
/* * 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]='