【DPメニュー】【部分列】最長減少部分列 (paizaランク B)-解答例-PHP編

2022年8月16日

【DPメニュー】> FINAL問題【部分列】最長減少部分列 (paizaランク B 相当) [難易度: 1646 ±19]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

n 本の木が横一列に並んでいます。左から i 番目の木を木 i と呼ぶことにします。木 i の高さは a_i [cm] です。

あなたは、何本かの木を伐採することによって、残った木を左から順に見ると高さが単調減少になっているようにしたいと考えています。つまり、残った木を左から木 k_1, 木 k_2, ... , 木 k_m とすると、a_{k_1} > a_{k_2} > ... > a_{k_m} が満たされているようにしたいです。なるべく多くの木が残るように工夫して伐採する木を選んだとき、伐採されずに残る木の本数が最大でいくつになるか求めてください。

なお、最初から n 本の木が単調減少に並んでいる場合は、1本も伐採しなくてよいものとします。

入力値（例）
5
109
110
108
103
100

出力値（例）
4

解答例

<?php
    $n = trim(fgets(STDIN));
    
    for ($i = 0; $i < $n; $i++) {
        $a[] = trim(fgets(STDIN));
    }
    
    for ($i = 0; $i < $n; $i++) {
        $dp[$i] = 1;
        for ($j = 0; $j < $i; $j++) {
            if ($a[$j] > $a[$i]) {
                $dp[$i] = max($dp[$i], $dp[$j]+1);
            }
        }
    }

    echo max($dp);
?>

<?php

$n = trim(fgets(STDIN));

for ($i = 0; $i < $n; $i++) {

$a[] = trim(fgets(STDIN));

}

for ($i = 0; $i < $n; $i++) {

$dp[$i] = 1;

for ($j = 0; $j < $i; $j++) {

if ($a[$j] > $a[$i]) {

$dp[$i] = max($dp[$i], $dp[$j]+1);

}

echo max($dp);

解答例

カテゴリー