二次元 DP 基礎 1 R(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
この問題集では動的計画法を用いて解くことができる問題を扱います。
特に、この問題集のすべての問題は DP テーブルを二次元 (dp[*][*] の形) で考えることができます。
この問題集を通して動的計画法をマスターしましょう。
H 行 W 列のグリッドがあります。
上から i 番目、左から j 番目のマスをマス (i, j) と表します。
グリッド上には M 個のチェックポイントがあり、k 個目のチェックポイントはマス (p_k, q_k) にあります。
あなたは最初マス (1,1) におり、マス (i,j) にいるときマス (i+1,j), (i,j+1) に移動できます。
ただし、グリッドの外に出るような移動はできません。
マス (1,1) からマス (H,W) に移動するとき、通ったマスに含まれるチェックポイントの個数の最大値を求めてください。
入力例 1 では、例えば、(1,1) → (1,2) → (2,2) → (2,3) → (3,3) と移動することができ、このとき通ったチェックポイントの個数は 2 です。
3 つのチェックポイントを通って移動することはできないので 2 を出力します。
- 入力される値
-
入力は以下のフォーマットで与えられます。
H W M
p_1 q_1
p_2 q_2
...
p_M q_M
・1 行目には、グリッドのサイズを表す整数 H,W、チェックポイントの個数を表す整数 M が与えられます。
・続く M 行には、チェックポイントの座標が与えられます。
・入力は合計で M+1 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
マス (1,1) からマス (H,W) に移動するとき、通ったマスに含まれるチェックポイントの個数の最大値を求めてください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ H,W ≦ 500
・1 ≦ M ≦ min(2 × 10^4, H * W - 1)
・1 ≦ p_k ≦ H
・1 ≦ q_k ≦ W
・(p_k, q_k) ≠ (1, 1)
・(p_k, q_k) ≠ (p_l, q_l) (k ≠ l)
- 入力例1
-
3 3 3
1 2
3 1
2 3
- 出力例1
-
2
- 入力例2
-
10 5 10
6 2
10 5
3 4
3 1
10 4
5 1
6 3
7 2
9 1
1 3
- 出力例2
-
6
- 入力例3
-
100 100 20
90 85
95 14
78 7
85 49
46 42
36 16
53 44
37 27
73 89
31 92
98 2
66 65
61 29
3 5
53 15
31 88
98 1
4 31
75 24
24 24
- 出力例3
-
7
