求出一個(gè)連續(xù)子序列，這個(gè)子序列由三部分ABC構(gòu)成，其中AB是回文串，A和C相同，也就是BC也是回文串。

求這樣一個(gè)最長的子序列。

Manacher算法是在所有兩個(gè)相鄰數(shù)字之間插入一個(gè)特殊的數(shù)字，比如-1，

Manacher算法跑完之后，就計(jì)算出每個(gè)數(shù)字為中心的回文子序列的最大長度

由題意可以知道，AB和BC必然是長度為偶數(shù)的回文串。所以我們枚舉回文串的中心就枚舉相鄰兩個(gè)數(shù)字之間的縫隙，也就是那些-1

把AB中間的間隙叫做左中心i，BC之間的間隙叫做右中心j，那么如果兩個(gè)中心的范圍能夠互相覆蓋，那么就找到一個(gè)符合條件的連續(xù)子序列。

做法就是枚舉左中心i，在左中心的范圍內(nèi)枚舉右中心j，然后維護(hù)一個(gè)最大值即可。

在枚舉j的時(shí)候不要直接從[i+1, i + p[i] - 1]枚舉，會(huì)超時(shí)的。

比如說我們維護(hù)的最大值是ans，那么直接從 i + ans 開始枚舉，因?yàn)橹暗膮^(qū)間即使找到合法子序列也并不能更新這個(gè)最大值。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 100000 + 10; 8 9 int n, tot; 10 int a[maxn], b[maxn * 2]; 11 12 int p[maxn * 2]; 13 14 void Manacher() 15 { 16 int id, mx = 0; 17 p[0] = 0; 18 for(int i = 1; i < tot; i++) 19 { 20 if(mx > i) p[i] = min(p[id * 2 - i], mx - i); 21 else p[i] = 1; 22 while(b[i + p[i]] == b[i - p[i]]) p[i]++; 23 if(i + p[i] > mx) { mx = i + p[i]; id = i; } 24 } 25 } 26 27 int main() 28 { 29 int T; scanf("%d", &T); 30 for(int kase = 1; kase <= T; kase++) 31 { 32 scanf("%d", &n); 33 for(int i = 0; i < n; i++) scanf("%d", a + i); 34 35 b[0] = -2, b[1] = -1; 36 tot = 2; 37 for(int i = 0; i < n; i++) 38 { 39 b[tot++] = a[i]; 40 b[tot++] = -1; 41 } 42 43 Manacher(); 44 45 int ans = 1; 46 for(int i = 3; i < tot; i += 2) 47 { 48 for(int j = ans; j <= p[i]; j += 2) 49 if(p[i + j - 1] >= j) ans = j; 50 } 51 52 ans = ans / 2 * 3; 53 printf("Case #%d: %d\n", kase, ans); 54 } 55 56 return 0; 57 } 代碼君

?

轉(zhuǎn)載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4732720.html

總結(jié)

以上是生活随笔為你收集整理的HDU 5371 Manacher Hotaru's problem的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。