Problem
クロエは最近、電話に Zuma をインストールしました。プレイヤーには n 個の宝石が与えられ、その i 番目の色は c
i です。ゲームの目的 —できるだけ数秒ですべての石を破壊してください。
クロエは 1 秒で、回文である部分文字列 (一連の隣接する石) を選択して削除できます。このサブストリングを取り除いた後、残りの石をずらして、再び連続した列を形成します。ライン全体を破壊するのに必要な最小秒数は?
文字列 (または部分文字列) は、右から左に読むのと同じように左から右に読む場合、回文であることを思い出してください。この場合、これは、最初の石の色が最後の石の色に等しく、2 番目の色が最後から 2 番目の石の色に等しい、ということを意味します。
入力:
入力の最初の行には、単一の整数 n (1 ≤ n ≤ 500) — が含まれます。最初の列の石の数。
2 行目には n 個の整数が含まれ、その i 番目は c
i (1 ≤ c
i ≤ n) に等しくなります。 ;最初の行の i 番目の石の色。
出力:
単一の整数を出力します —すべてのジェムを削除するのに必要な最小秒数。
例:
<本体>
| 入力 |
出力 |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
説明:
3 番目の例のシーケンスは [1, 4, 4, 2, 3, 2, 1] -> です。 [1, 4, 4, 1] -> []