洛谷1091合唱隊形

題目描述

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

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

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

輸入輸出格式

輸入格式：

?

共二行。

第一行是一個整數N(2≤N≤100)，表示同學的總數。

第二行有n個整數，用空格分隔，第i個整數(130≤Ti?≤230)是第ii位同學的身高(厘米)。

?

輸出格式：

?

一個整數，最少需要幾位同學出列。

?

輸入輸出樣例

輸入樣例#1：?復制

8
186 186 150 200 160 130 197 220

輸出樣例#1：?復制

4

說明

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

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

?

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int i,j,n,a[105],f[2][105],ans;
int main()
{
    scanf("%d",&n);
    for(i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
    }
    a[0] = 0;
    for(i = 1;i <= n;i++)//從1到n求最長列 
    {
        for(j = 0;j <= i;j++)
        {
            if(a[i] > a[j])
            f[0][i] = max(f[0][i],f[0][j] + 1);
        }
    }
    a[n + 1] = 0;
    for(i = n;i >= 1;i--)//從n到1求最長列 
    {
        for(j = n + 1;j > i;j--)
        {
            if(a[i] > a[j])
            f[1][i] = max(f[1][i],f[1][j] + 1);
        }
    }
    for(i = 1;i <= n;i++)
    {
        ans = max(f[0][i] + f[1][i] - 1,ans);//枚舉Ti,從1到Ti的最長列+從TK到Ti的最長列- 1（Ti被加了兩次)
    }
    printf("%d",n - ans);
    return 0;
 } 

*****顯然這個是一個區間DP呦，從前往后求最長上升序列，然后求從后往前求最長上升序列，最后枚舉中間人的位置求出答案，吼吼吼