合唱隊形

題目來源：NOIP2004提高組
時間限制：\(1000ms\) 記憶體限制：\(128mb\)

題目描述

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

輸入格式

輸入的第一行是一個整數 \(N\) ，表示同學的總數，
第二行有 \(N\) 個整數，用空格分隔，第 \(i\) 個整數 \(T_i\) 是第 \(i\) 位同學的身高(厘米)，

輸出格式

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

資料范圍

\(2 ≤N ≤ 100\) ,
\(130 ≤ T_i ≤ 230\)

樣例輸入

8
186 186 150 200 160 130 197 220

樣例輸出

解題思路

要使所有同學的身高呈現出先遞增后遞減的格式，需要將中間比較突出的同學請出列，
先設定一個中間點，中間點將左右兩邊分開，只需要使左右兩邊分別剔除的同學最少，再將左右兩邊相加即可，
由于分成了左右兩邊，于是只需要計算左邊的最長遞增子序列，右邊反過來的最長遞增子序列，然后把它們加起來就得到了需要的同學的數量，
然后用總數減去需要的同學的數量就得到了需要剔除的同學的數量，

解題代碼

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = input.nextInt();
        }
        input.close();

        int[] f = new int[n], g = new int[n];

        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (t[j] < t[i]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            g[i] = 1;
            for (int j = n - 1; j >= i; j--) {
                if (t[j] < t[i]) {
                    g[i] = Math.max(g[i], g[j] + 1);
                }
            }
        }

        int ans = 0;
        for (int k = 0; k < n; k++) {
            ans = Math.max(ans, f[k] + g[k] - 1);
        }

        System.out.println(n - ans);
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253428.html

標籤：其他

上一篇：kubeadm部署kubernetes·高可用集群

下一篇：2021寒假每日一題《火星人》

2021寒假每日一題《合唱隊形》