[ACM] 九度OJ 合唱隊形 （最長遞增子序列改版）

時間限制：1 秒

內存限制：32 兆

特殊判題：否

提交：1680

解決：520

N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學不交換位置就能排成合唱隊形。
合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1, 2, …, K，他們的身高分別為T1, T2, …, TK，
則他們的身高滿足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。
你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。

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

可能包括多組測試數據，對於每組數據，
輸出包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。

8
186 186 150 200 160 130 197 220

4

解題思路：

給N個數，從中剔除K個數，要求剩下數的序列成先上升後下降的狀態。求最小的K。

對於N中的每一個數，都以它為“最高點”，求以它為結尾的最長遞增子序列和以它為結尾的最長遞減子序列的長度之和（注意該數被計算了兩次，最後要減去1），那麼總長度減去長度之和，就為K的大小。dpup[i]存的是以num[i]為結尾的最長遞增子序列的長度，dpdown[i]存的是以num[i]為開頭的最長遞減子序列。枚舉每個數就可以了，求出裡面最大的長度之和，K減去它+1就是答案。這裡計算最長遞增子序列不用二分查找那種效率高的方法，而用dp[i]代表以num[i]為結尾的最長遞增子序列的長度，因為它記錄了其中每個數當結尾的最長遞增子序列長度。求最長遞減子序列也就是求尾到頭求最長遞增子序列。這樣dpup[i]就是存的以num[i]為結尾的最長遞增子序列的長度，dpdown[i]就是存的以num[i]為開頭的最長遞減子序列的長度。

代碼：

#include 
#include 
using namespace std;
int num[102];
int dpup[102];//dpup[i]以num[i]為結尾的最長上升子序列
int dpdown[102];//dpdown[i]以num[i]為開頭的最長遞減子序列
int n;

void LIS(int num[],int n)//最長上升子序列
{
    int m;
    dpup[1]=1;
    for(int i=2;i<=n;i++)
    {
        m=0;
        for(int j=1;jm&&num[j]=1;i--)
    {
        m=0;
        for(int j=n;j>i;j--)
        {
            if(dpdown[j]>m&&num[j]