1264：【例9.8】合唱隊形

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 10735 ??? 通過數: 5283

【題目描述】

N位同學站成一排，音樂老師要請其中的(N?K)位同學出列，使得剩下的K位同學排成合唱隊形。

合唱隊形是指這樣的一種隊形：設KK位同學從左到右依次編號為1,2,…,K，他們的身高分別為T1,T2,…,TK，則他們的身高滿足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。

你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。

【輸入】

輸入的第一行是一個整數N（2≤N≤100），表示同學的總數。第二行有n個整數，用空格分隔，第ii個整數Ti（130≤Ti≤230）是第ii位同學的身高（厘米）。

【輸出】

輸出包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。

【輸入樣例】

8 186 186 150 200 160 130 197 220

【輸出樣例】

4

【提示】

對于50%的數據，保證有n≤20；

對于全部的數據，保證有n≤100。

【分析】

? ? ? ? 出列人數最少，也就是留的人數最多，也就是序列最長，我們按照由左而右和由右而左的順序，將n個同學的身高排成數列。如何分別在這兩個數列中尋求遞增的、未必連續的最長上升子序列和遞減的、未必連續的最長下降子序列就成為問題的關鍵。設
????????a為身高序列，其中 a[i]為同學 i 的身高。
????????b為由左而右身高遞增的人數序列，其中 b[i]為同學 1…同學 i 間（包括同學 i）身高滿足遞增順序的最多人數。顯然b[i] = max { b[j] | 同學 j 的身高 < 同學 i 的身高 +1，1<=j<=i-1 }。
????????c為由右而左身高遞增的人數序列，其中 c[i]為同學 n…同學 i 間（包括同學 i）身高滿足遞增順序的最多人數。顯然 c[i] = max { c[j] | 同學 j 的身高 < 同學 i 的身高 +1，i+1<=j<=n }。
? ? ? ? 顯然，合唱隊的人數為max { b[i]+c[i] } -1（公式中的同學 i 被重復計算，因此減1）。數據存儲和求解過程如下：

?前面采用順推實現，后面采用逆推實現。樣例數據需要186、186、197和220這四個同學出列。

【參考代碼】

#include <stdio.h> #define N 110 int a[N]; int b[N]; // 以第i位同學為終點的最長上升序列的長度 int c[N]; // 以第i位同學為起點的最長下降序列的長度 int ans; int main() {int i,j,n;int maxn;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);// 以第i位同學為終點的最長上升序列b[1]=1;for(i=2;i<=n;i++){maxn=0;for(j=1;j<i;j++){if(a[i]>a[j]){if(b[j]>maxn)maxn=b[j];}}b[i]=maxn+1;}// 以第i位同學為起點的最長下降序列c[n]=1;for(i=n-1;i>=1;i--){maxn=0;for(j=i+1;j<=n;j++){if(a[i]>a[j]){if(c[j]>maxn)maxn=c[j];}}c[i]=maxn+1;}for(i=1;i<=n;i++)if(b[i]+c[i]>ans)ans=b[i]+c[i];printf("%d\n",n-(ans-1));return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1264

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1264：【例9.8】合唱队形）的全部內容，希望文章能夠幫你解決所遇到的問題。

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