文字列を値にもつ DP、ご無沙汰！！！

問題概要

$N$ 本のマッチ棒を使ってできるだけ大きな数値を作りたい。
マッチ棒で 1, 2, 3, 4, 5, 6, 7, 8, 9 を作るのにそれぞれ 2, 5, 5, 4, 5, 6, 3, 7, 6 本のマッチ棒が必要である。

ただし各桁に用いることのできる数値は $A_1, A_2, \dots, A_M$ のみに限られる ( $1 \le A_i \le 9$ )。

例えば、5 本のマッチ棒があったら、"71" を作ることができて、それが最大になる (7 に 3 本使って、1 に 2 本使う)。

制約

$2 \le N \le 10^{4}$

考えたこと

考え方としては ABC 099 C 問題 - Strange Bank とかとまったく同じような DP でできそう。

ただし、作られる数が long long 型ではおさまらないので、string 型で数値を管理する必要が出てくる。まずはその扱い方に関する考察を抜きにして、DP を組んでみる。

dp[ i ] := マッチ棒を i 本使って作れる数値の最大値

とする。これに対し、各 a = $A_1, A_2, \dots, A_M$ に対して、

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;
}