HDU 4513 哥几个系列故事——形成完善II manacher求最长回文
系列 HDU 几个 II 最长 故事 回文 完善
2023-09-14 09:08:10 时间
标题来源:哥几个系列故事——形成完善II
意甲冠军:中国
思维:在manacher断 保证非严格递减即可了
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100110; int a[maxn<<1]; int b[maxn<<1]; int dp[maxn<<1]; int manacher(int n) { int maxlen = 0, id, ans = 0; for(int i = 1; i < n; i++) { if(maxlen > i) dp[i] = min(dp[id*2-i], maxlen-i); else dp[i] = 1; int flag = 0, x = 1; if(a[i] != 1) { flag = 1; x = a[i]; } while(a[i+dp[i]] == a[i-dp[i]]) { if(a[i+dp[i]] == 1) dp[i]++; else { if(!flag) { x = a[i+dp[i]]; dp[i]++; flag = 1; } else { if(a[i+dp[i]] > x) break; x = a[i+dp[i]]; dp[i]++; } } } if(dp[i]+i > maxlen) { id = i; maxlen = dp[i]+i; } if(ans < dp[i]) ans = dp[i]; } return ans-1; } int main() { int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); a[0] = -1; a[1] = 1; for(int i = 1; i <= n; i++) { scanf("%d", &a[i<<1]); a[i<<1|1] = 1; } n = n*2+2; a[n] = 2; printf("%d\n", manacher(n)); } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
相关文章
- React系列——websocket群聊系统在react的实现
- Kubernetes系列之介绍篇(转)
- Spring4.0系列9-websocket简单应用
- hbase源码系列(二)HTable 探秘
- sql 语句系列(计算一个季度的开始日期和结束日期)[八百章之第二十三章]
- Atitit atiuse软件系列
- ML:MLOps系列讲解之《基于ML的软件的三个层次之02 Model: Machine Learning Pipelines——2.5 Different forms of ML workfl》解读
- 带着canvas去流浪系列之三 绘制饼图
- 【成为架构师课程系列】消息队列:秒杀时如何处理每秒上万次的下单请求?
- Kubernetes基础自学系列 | 调度器
- 【云原生 | Kubernetes 系列】--Gitops持续交付 ArgoCD 部署与概念