吉哥系列故事——完美隊形II

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)

Problem Description 吉哥又想出了一個新的完美隊形游戲！
　　假設有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]。

　　現在吉哥想知道：最多能選出多少人組成新的完美隊形呢？
Input 輸入數據第一行包含一個整數T，表示總共有T組測試數據(T <= 20)；
　　每組數據首先是一個整數n(1 <= n <= 100000)，表示原先隊形的人數，接下來一行輸入n個整數，表示原隊形從左到右站的人的身高（50 <= h <= 250，不排除特別矮小和高大的）。
Output 請輸出能組成完美隊形的最多人數，每組輸出占一行。
Sample Input 2 3 51 52 51 4 51 52 52 51
Sample Output 3 4解題思路：首先用manacher算法求出每個字符的回文半徑，接下來就是如何求非遞減的串了，這里可以用dp的思想，dp[i]表示以s[i]結尾的最長非遞減子串。那么只需要比較dp[i]與r[i]/2的大小關系即可。總之還是比較容易想的。#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; int n,H[maxn],c[maxn<<1]; int dp[maxn],r[maxn<<1];void Manacher() {int id,maxlen;r[0] = 1;maxlen = 0;id = 0;for(int i = 1; i <= 2*n; i++){if(r[id] + id > i) r[i] = min(r[2*id-i],r[id] + id - i);else r[i] = 1;while(c[i - r[i]] == c[i + r[i]]) r[i]++;if(i + r[i] > maxlen){maxlen = i + r[i];id = i;}} }int main() {int t,id;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&H[i]);c[0] = -1;for(int i = 1; i <= n; i++){c[2*i] = 0;c[2*i-1] = H[i];}c[2*n] = -2;dp[1] = 1; for(int i = 2; i <= n; i++) //dp[i]表示以H[i]結尾的最長非遞減子串{if(H[i] >= H[i-1])dp[i] = dp[i-1] + 1;else dp[i] = 1;}Manacher();int ans = 0;for(int i = 1; i <= 2*n; i++){if(i % 2 == 1){id = (i + 1) / 2;ans = max(ans,2 * min((r[i] + 1)/2,dp[id]) - 1);}else{id = i / 2;ans = max(ans,2 * min(r[i]/2,dp[id]));}}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4513(manacher+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。