HDU 3613 Best Reward 正反两次扩展KMP

2024-06-15 11:38

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063347

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin