HDU 4513 吉哥系列故事――完美队形II(Manacher)
2024-10-21 17:37:02
题目链接: cid=70325#problem/V">[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher V - 吉哥系列故事――完美队形II
题意
吉哥又想出了一个新的完美队形游戏!
如果有n个人按顺序站在他的面前,他们的身高各自是h[1], h[2] … h[n],吉哥希望从中挑出一些人。让这些人形成一个新的队形,新的队形若满足下面三点要求,则就是新的完美队形:
1、挑出的人保持原队形的相对顺序不变。且必须都是在原队形中连续的;
2、左右对称,如果有m个人形成新的队形,则第1个人和第m个人身高同样,第2个人和第m-1个人身高同样。依此类推,当然如果m是奇数,中间那个人能够随意。
3、从左到中间那个人,身高需保证不下降,如果用H表示新队形的高度,则H[1] <= H[2] <= H[3] …. <= H[mid]。如今吉哥想知道:最多能选出多少人组成新的完美队形呢?
思路
跟HDU 3068 最长回文(Manacher)差点儿相同,也是求回文串长度,差别就是多了一个非递减的约束条件,加上推断就可以。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
const int N = 100009;
int s[N*2], p[N*2];
int manacher(int len)
{
int mx = 0, id = 0, ans = 1;
p[0] = 0;
for(int i=1; i<len; i++)
{
p[i] = 1;
if(mx > i)
p[i] = min(mx-i, p[2*id-i]);
while(s[i-p[i]] == s[i+p[i]] && s[i-p[i]] <= s[i-p[i]+2])
p[i]++;
if(i+p[i] > mx)
mx = i+p[i], id = i;
if(ans < p[i]-1)
ans = p[i]-1;
}
return ans;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
s[0] = -1;
for(int i=1; i<=n; i++)
{
s[i*2-1] = 0;
scanf("%d", &s[i*2]);
}
s[2*n+1] = 0;
printf("%d\n", manacher(2*n+1));
}
return 0;
}
最新文章
- 维特比算法(Viterbi Algorithm)
- Nginx 学习
- [USACO2004][poj2375]Cow Ski Area(在特殊图上用floodfill代替强联通算法)
- Swift - 15 - 导入Foundation使用更多字符串功能
- ASP.NET-FineUI开发实践-7
- VIM在文件夹中查找
- Songs
- iOS 之 const
- Android常用开发工具的用法
- 【Qt编程】基于Qt的词典开发系列<;十>;--国际音标的显示
- Leetcode 树(102, 637)
- vue中复选框全选与反选
- 【开发工具之eclipse】7、eclipse代码自动提示,eclipse设置代码自动提示
- nginx的安装应用
- 51nod 1277 字符串中的最大值
- sjw-风评评测-定位页面元素
- Centos7安装JDK8以及环境配置
- DBS-Tally book(记账本)
- C# IOCP服务器项目(学习)
- Linux HugePages 配置与 Oracle 性能关系说明