[伯俊]2631列-javascript

📌 質問する

https://www.acmicpc.net/problem/2631

📌 に答える

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const N = +input.shift();
const arr = input.map((i) => +i);
const longest = new Array(N).fill(1);

for (let i = 1; i < N; i++) {
  let cnt = 0;
  for (let j = 0; j < i; j++) {
    if (arr[j] < arr[i]) cnt = Math.max(cnt, longest[j]);
  }
  longest[i] = cnt + 1;
}

console.log(N - Math.max(...longest));

✔アルゴリズム:DP
✔は異動者を順番に配置する必要がある問題です
✔現在の順序で並べられている最大部分の数列の長さを求め、全体の人数を差し引くと、最小の順序で並べられます
✔二重forゲート、最大増加部分数列の長さを求め、減算すればよい.
✔難易度:標準プラチナ5