[BOJ]2631-行列

問題の説明
この問題で注意しなければならないのは、子供たちの順番がはっきりしていることです.Nと同じように並ぶべきです.
したがって,この要求を満たすためには,順序を守った友人を排除する必要はない.
例えば、1、3、4、5、2が一緒に立つと、順番を守っている友達は1、3、4または1、3、5になります.
順序違反の5,2あるいは4,2については,前と後のシミュレーションを除いても必要であるが,この問題では,遷移の最小数を求めることが核心である.
上記の手順を守っている友人を知るために必要な概念は,Longest Increating Subsequence(LIS)アルゴリズムである.
これは無条件にDPを用いる必要があり,時間的複雑さはO(n 2)またはO(nlogn)で行うことができる.
そしてこの値を求めると、すべての友人の数から順序違反の友人の数を減算して完成します.
質問リンク
https://www.acmicpc.net/problem/2631
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// LIS 알고리즘만 생각하면 단숨에 풀 수 있다.
public class Solve2631 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] children = new int[N];
        for (int i = 0; i < N; i++) {
            children[i] = Integer.parseInt(br.readLine());
        }

        int stay = 0;
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (children[j] < children[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            stay = Math.max(stay, dp[i]);
        }

        System.out.println(N - stay);
    }
}