NOIP2004提高組 合唱隊形 chorus 解題報告

【問題描述】

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個整數Ti(130<=Ti<=230)是第i位同學的身高(釐米)。

【輸出文件】

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

【樣例輸入】

8

186 186 150 200 160 130 197 220

【樣例輸出】

4

【數據規模】

對於50％的數據，保證有n<=20；

對於全部的數據，保證有n<=100。

【分析】
動態規劃，本題實際上是求最長下降序列、最長上升序列問題。
注意：最長下降序列、最長上升序列有且只有一個公共點，就是以同一個人為中心，向兩邊DP。

//NOIP2004-chorus
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int H[101];
int X[101];//X[i]是以i為開頭的最長下降序列
int S[101];//S[i]是以i為結尾的最長上升序列
int n;

void init()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&H[i]);
}

int dp()
{
    int maxn=0;
    for (int k=1;k<=n;k++)
    {
        //先DP出最長上升序列
        memset(S,0,sizeof(S));
        S[1]=1;
        for (int i=2;i<=k;i++)
        {
            S[i]=1;
            for (int j=1;j<=i-1;j++)
            {
                if(H[i]>H[j] && S[j]+1>S[i])
                    S[i]=S[j]+1;
            }
        }
       
        //再求最長下降序列
        memset(X,0,sizeof(X));
        X[n]=1;
        for (int i=n-1;i>=k;i--)
        {
            X[i]=1;
            for (int j=i+1;j<=n;j++)
            {
                if(H[i]>H[j] && X[j]+1>X[i])
                    X[i]=X[j]+1;
            }
        }
       
        if (X[k]+S[k]>maxn)
            maxn=X[k]+S[k];
    }
    return maxn-1;
}

int main()
{
    freopen("chorus.in","r",stdin);
    freopen("chorus.out","w",stdout);
    init();
    printf("%d\n",n-dp());
    return 0;
}

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.023 s	272 KB	0
2	正确	10	0.001 s	272 KB	0
3	正确	10	0.001 s	272 KB	0
4	正确	10	0.001 s	272 KB	0
5	正确	10	0.001 s	272 KB	0
6	正确	10	0.003 s	272 KB	0
7	正确	10	0.003 s	272 KB	0
8	正确	10	0.003 s	272 KB	0
9	正确	10	0.003 s	272 KB	0
10	正确	10	0.003 s	272 KB	0

运行完成
运行时间 0.040 s
平均内存使用 272 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!