hu3613 Best Reward
地址:http://acm.hdu.edu.cn/showproblem.php?pid=3613
题目:
Best Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2326 Accepted Submission(s): 944
One of these treasures is a necklace made up of 26 different kinds of gemstones, and the length of the necklace is n. (That is to say: n gemstones are stringed together to constitute this necklace, and each of these gemstones belongs to only one of the 26 kinds.)
In accordance with the classical view, a necklace is valuable if and only if it is a palindrome - the necklace looks the same in either direction. However, the necklace we mentioned above may not a palindrome at the beginning. So the head of state decide to cut the necklace into two part, and then give both of them to General Li.
All gemstones of the same kind has the same value (may be positive or negative because of their quality - some kinds are beautiful while some others may looks just like normal stones). A necklace that is palindrom has value equal to the sum of its gemstones' value. while a necklace that is not palindrom has value zero.
Now the problem is: how to cut the given necklace so that the sum of the two necklaces's value is greatest. Output this value.
For each test case, the first line is 26 integers: v1, v2, ..., v26 (-100 ≤ vi ≤ 100, 1 ≤ i ≤ 26), represent the value of gemstones of each kind.
The second line of each test case is a string made up of charactor 'a' to 'z'. representing the necklace. Different charactor representing different kinds of gemstones, and the value of 'a' is v1, the value of 'b' is v2, ..., and so on. The length of the string is no more than 500000.
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aba
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
acacac
6
思路:扩展kmp
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio> using namespace std;
const int K=1e6+;
int nt[K],extand[K],v[],sum[K],l[K],r[K];
char sa[K],sb[K];
void Getnext(char *T,int *next)
{
int len=strlen(T),a=;
next[]=len;
while(a<len- && T[a]==T[a+]) a++;
next[]=a;
a=;
for(int k=; k<len; k++)
{
int p=a+next[a]-,L=next[k-a];
if( (k-)+L >= p)
{
int j = (p-k+)> ? (p-k+) : ;
while(k+j<len && T[k+j]==T[j]) j++;
next[k]=j;
a=k;
}
else
next[k]=L;
}
}
void GetExtand(char *S,char *T,int *next)
{
Getnext(T,next);
int slen=strlen(S),tlen=strlen(T),a=;
int MinLen = slen < tlen ? slen : tlen;
while(a<MinLen && S[a]==T[a]) a++;
extand[]=a;
a=;
for(int k=; k<slen; k++)
{
int p=a+extand[a]-, L=next[k-a];
if( (k-)+L >= p)
{
int j= (p-k+) > ? (p-k+) : ;
while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
extand[k]=j;
a=k;
}
else
extand[k]=L;
}
}
int main(void)
{
int t;cin>>t;
while(t--)
{
int ans=;
for(int i=;i<;i++)
scanf("%d",v+i);
scanf("%s",sa);
int len=strlen(sa);
for(int i=;i<len;i++)
sb[i]=sa[len-i-];
sum[]=v[sa[]-'a'];
for(int i=;i<len;i++)
sum[i]=sum[i-]+v[sa[i]-'a'];
sb[len]='\0';
GetExtand(sb,sa,nt);
for(int i=;i<len;i++)
if(extand[i]==len-i) l[len-i-]=;
else l[len-i-]=;
GetExtand(sa,sb,nt);
for(int i=;i<len;i++)
if(extand[i]==len-i) r[i]=;
else r[i]=;
for(int i=;i<len-;i++)
{
int tmp=;
if(l[i]) tmp+=sum[i];
if(r[i+]) tmp+=sum[len-]-sum[i];
ans=max(ans,tmp);
}
printf("%d\n",ans);
}
return ;
}
最新文章
- ADO.NET数据库参数化
- zookeeper多节点配置
- iOS 最全面试题
- Bungie Interview with Halo3 Developer
- linux下遍历目录(转-在于思考)
- POJ-1488(字符串应用)
- 製程能力介紹(SPC introduction) ─ 製程能力改善及評估
- uvalive4015 (树上背包)
- POJ 3139 Balancing the Scale
- ajax通过设置Access-Control-Allow-Origin来实现跨域访问
- java库中的具体的集合
- Java入门(三):变量和运算符
- bowtie:短序列比对的新工具
- java基础-day12
- CentOS7安装MySQL5.7常见问题
- mysql 数据操作 多表查询 多表连接查询 全外连接
- DCloud开发资源链接
- vue-router和锚点冲突问题
- P1330 封锁阳光大学 DFS+染色
- vijos:P1155集合位置(次短路)
热门文章
- hdu 1086:You can Solve a Geometry Problem too(计算几何,判断两线段相交,水题)
- 利用flume+kafka+storm+mysql构建大数据实时系统
- Python Scrapy 自动爬虫注意细节(3)
- Splash界面完美实现
- box-sizing在什么情况下会失效
- oracle数据库查询时间sql
- TClientDataSet数据源设置
- java基础---->;Java中异常的使用(一)
- 【BZOJ2801】[Poi2012]Minimalist Security BFS
- 知问前端——html+jq+jq_ui+mySql+ajax