文字列を値にもつ DP、ご無沙汰!!!
問題概要
本のマッチ棒を使ってできるだけ大きな数値を作りたい。
マッチ棒で 1, 2, 3, 4, 5, 6, 7, 8, 9 を作るのにそれぞれ 2, 5, 5, 4, 5, 6, 3, 7, 6 本のマッチ棒が必要である。
ただし各桁に用いることのできる数値は のみに限られる ()。
例えば、5 本のマッチ棒があったら、"71" を作ることができて、それが最大になる (7 に 3 本使って、1 に 2 本使う)。
制約
考えたこと
考え方としては ABC 099 C 問題 - Strange Bank とかとまったく同じような DP でできそう。
ただし、作られる数が long long 型ではおさまらないので、string 型で数値を管理する必要が出てくる。まずはその扱い方に関する考察を抜きにして、DP を組んでみる。
- dp[ i ] := マッチ棒を i 本使って作れる数値の最大値
とする。これに対し、各 a = に対して、
- chmax(dp[ i + match[ a ] ], dp[ i ] の末尾に "a" を加えたもの)
という感じの遷移を実施すれば OK。match[ a ] は a を作るのに必要なマッチ棒の本数を表す。
数値を表す文字列の扱い
さて、もし答えが long long 型でおさまるなら
- chmax(dp[ i + match[ a ] ], dp[ i ] × 10 + a)
とかで OK。例えば dp[ i ] = "765" のとき、a = '2' を付け加えると "7652" となって、これは dp[ i ] × 10 + a になっている。
しかし、今回は long long 型がダメなので dp 配列の値を string 型でもつことにする。そうすると単純に '+' 演算子を用いて、
- chmax(dp[ i + match[ a ] ], dp[ i ] + "a")
という感じで組めることになる。問題なのはこの chmax 処理だ!!!!!!!!!!!!!
これをそのまんま文字列としての大小比較をしてはいけない。例えば
- 999
- 1111111111
とでは明らかに後者の方が大きいが、文字列としては前者の方が大きくなってしまう (文字列の大小関係は辞書順)。数値を文字列で表すとき、大小関係は
- サイズが大きいならば、桁数が大きいということなので、無条件に大きい
- サイズが等しいならば、文字列としての辞書順が大きい方が大きい
として実現することができる。最後に、dp テーブルを初期化する上での -INF を表す文字列を別途設定しておいた。
#include <iostream> #include <string> #include <vector> using namespace std; const string MINUSINF = "-"; void chmax(string &a, string b) { if (a == MINUSINF) a = b; else if (a.size() < b.size()) a = b; else if (a.size() == b.size()) { if (a < b) a = b; } } long long match[10] = {2,5,5,4,5,6,3,7,6}; string dp[11000]; int main() { int N, M; cin >> N >> M; vector<int> A(M); for (int i = 0; i < M; ++i) cin >> A[i]; // 初期化 for (int i = 0; i < 11000; ++i) dp[i] = MINUSINF; // 初期条件 dp[0] = ""; // DP ループ for (int i = 0; i <= N; ++i) { if (dp[i] == MINUSINF) continue; for (auto a : A) chmax(dp[i+match[a-1]], dp[i] + (char)('0' + a)); } cout << dp[N] << endl; }