最長嚴格遞增回文串 +hdu 4512
來源：程序員人生 發布時間：2016-04-13 08:26:22 閱讀次數：2530次
吉哥系列故事――完善隊形I
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2652 Accepted Submission(s): 862
Problem Description
吉哥這幾天對隊形比較感興趣。
有1天，有n個人按順序站在他的眼前，他們的身高分別是h[1], h[2] ... h[n]，吉哥希望從中挑出1些人，讓這些人構成1個新的隊形，新的隊形若滿足以下3點要求，則稱之為完善隊形：
1、挑出的人保持他們在原隊形的相對順序不變；
2、左右對稱，假定有m個人構成新的隊形，則第1個人和第m個人身高相同，第2個人和第m⑴個人身高相同，依此類推，固然，如果m是奇數，中間那個人可以任意；
3、從左到中間那個人，身高需保證遞增，如果用H表示新隊形的高度，則H[1] < H[2] < H[3] .... < H[mid]。
現在吉哥想知道：最多能選出多少人組成完善隊形？
Input
第1行輸入T，表示總共有T組數據(T <= 20)；
每組數據先輸入本來隊形的人數n(1<=n <= 200)，接下來1行輸入n個整數，表示按順序從左到右本來隊形位置站的人的身高（50 <= h <= 250，不排除特別矮小和高大的）。
Output
請輸出能組成完善隊形的最多人數，每組數據輸出占1行。
Sample Input
2
3
51 52 51
4
51 52 52 51
Sample Output
Source
2013騰訊編程馬拉松初賽第2場（3月22日）
鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4512
思路：由于不要連續，要回文且兩邊向中間嚴格遞增，所以我們可以這樣做，把序列的正串和反串分別存起來（固然也能夠不存反串，為了表述方便，我用a串表示正串，b串表示反串。）那末對a和b求----最長遞增公共子序列就能夠得到最長回文遞增子序列了。這里需要控制每次求最長遞增子序列的長度，即：正串當前位置求時，最多到達反串在正串本身的位置?。ㄓ悬c抽象，代碼中有注釋）
#include
#include
#includeusing namespace std;
int n,a[205],b[205];
int LICS()
{
int ans=0;//記錄答案，返回
int dp[205]={0};//dp[]用來記錄當前位置為回文中點的回文串長度的1半
for(int i=1;i<=n;i++) { int len=0;//回文串1半的長度 for(int j=1;j<=n-i+1;j++)/**j最多到達本身位置*/ { if(a[i]>b[j])
len=max(len,dp[j]);
else if(a[i]==b[j])
dp[j]=max(dp[j],len+1);
if(j
版權聲明：本文為博主原創文章，未經博主允許不得轉載。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
