ゆるふわ競プロ

Javaでゆるゆる競プロしています.忘れっぽいのでメモ用,復習用

ABC118 D (DP)

問題

DPの初歩的な問題でした。

解法

dp[i] : i本のマッチを使った時の最大桁数。

と定義してdp[N]を求めようと考えます.ここでは桁数だけを先に考えてあとで実際の数字になにが入るかを復元します。

dp[0] = 0

これが初期条件になる。マッチ0本を使って作ることのできる数列はありません。

もし与えられた条件に1という数字が入っていてコスト2の1を使って良いとするとdp[2] = 1となります。これは2本のマッチを使って1が作れることを示しています。

実際にdp[0] = 0の初期条件からどのようにdp[N]まで持っていくかを考えます.


マッチの数 : N
使って良い数字 : A_1 > A_2 > ... > A_m
それぞれに必要なマッチの本数 : num(A_i)


大きい数字を使いたいのでできるだけ Aの添え字が小さい数字を使うことを考える。

簡単な具体例で考える

dp[8] をどう考えるかについて話をしよう。ここで使える数字は<1,2>,<2,5>,<3,5>,<4,4><7,3>とする.(<数字,コスト>)を示している。

dp[0] = 0;
dp[1] = 0; // 実際にこれは定義されない
dp[2] = 1; 1
dp[3] = 1; 7
dp[4] = 2; 11
dp[5] = 2; 71
dp[6] = 3 ; 111
dp[7] = 3; 711
dp[8] = 4; 1111
結論から言うとこのようになる。
忘れないで欲しいことが

DP は前に使った結果を用いて現在の場所を計算する

これが本当に重要な考え方です。

dp[5] の求め方について考えていきましょう. dp[5] を求める時にdp[0] ~ dp[4] はすでに計算済みとします.(これがDPの考え方) 今回の条件では5本のマッチ棒全部を使わなくてはいけません。ここで5本を二つに分割していきます。(0,5),(1,4),(2,3),(3,2),(4,1),(5,0)の組み合わせになります。
(0,5) は dp[0] に 5本のマッチが新たに加えて5本のマッチを使ってできる数字一つを加えてできる数列を表します。

今回のコード

1        for (int i = 0; i < n + 1; i++) {
2           int max = -1;
3            String tar = "";
4          int pos = -1;
5          for (int j = 0; j < m; j++) {
6              int point = i - cost[a[j]];
7              if (point < 0)
8                  continue;
9              if (point != 0 && dp[point] == "") {

10             } else {
11                if (max < dp[point].length() + 1) {
12                     max = dp[point].length() + 1;
13                    tar = String.valueOf(a[j]);
14                    pos = point;
15                }
16            }
17        }
            if (max != -1) {
                dp[i] = tar + dp[pos];
            }
        }

9行目で配列外アクセスの防止と作れていない場合の例外処理を省いています。
13行目 : Integer のかたをString型に変換しています。

これぐらいの問題はコンテスト中にACできるようになりたいです。