二次元 DP 基礎 2 VB(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
横 1 列の N 個のマスがあります。
左から i 番目のマスをマス i とします。
これから時刻 T+0.5 にかけての各時刻では 1 枚ずつコインが出現します。
時刻 j+0.5 (1 ≦ j ≦ T) では、マス X_j にいる場合コインを 1 枚獲得できます。
最初あなたはマス 1 におり、時刻 t = 0 です。
これからあなたは各時刻 t = 1, 2, 3, ... T に以下の 2 種類の行動のいずれかを選び行動します。
・即座に右に 1 マス進む
・その場にとどまる
適切に行動した時、時刻 T+1 までに獲得できるコインの最大値を出力してください。
入力例 1 では、例えば以下のように行動できます。
・時刻 t = 1 ではマス 1 にとどまる。
・時刻 t = 1.5 ではマス 1 にいるのでコインを 1 枚獲得する。
・時刻 t = 2 では右に 1 マス進みマス 2 に移動する。
・時刻 t = 2.5 ではマス 3 にいないのでコインを獲得できない。
・時刻 t = 3 ではマス 2 にとどまる。
・時刻 t = 3.5 ではマス 2 にいるのでコインを 1 枚獲得する。
・時刻 t = 4 ではマス 2 にとどまる。
・時刻 t = 4.5 ではマス 4 にいないのでコインを獲得できない。
このように行動した時、時刻 5 までに獲得したコインは 2 枚です。
3 枚以上のコインを獲得できるように行動することはできないので、2 を出力します。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N T
X_1 X_2 ... X_T
・1 行目には、マスの個数を表す整数 N、コインが与えられる時刻の最大値 T が与えられます。
・2 行目には、各時刻にコインを手に入れることができるマスを表す数列 X が与えられます。
・入力は合計で 2 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
時刻 T+1 までに獲得できるコインの最大値を出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ T ≦ 3000
・1 ≦ X_i ≦ N
- 入力例1
-
4 4
1 3 2 4
- 出力例1
-
2
- 入力例2
-
5 6
5 5 5 5 2 1
- 出力例2
-
1
- 入力例3
-
10 20
7 1 9 6 6 6 10 9 7 10 10 6 4 1 6 9 2 5 9 3
- 出力例3
-
5
