概要
1から9までの数字のうち、使用してよい数字があらかじめ与えられる。
使用してよい数字を使ってできる最大の整数を求めよ。ただし、各数字を1つ作る度にコストがそれぞれ2, 5, 5, 4, 5, 6, 3, 7, 6かかるものとし、コストの合計がちょうどNになるように整数を作るものとする。（問題ではコスト=残りマッチ棒）
（コストは各数字のデジタル表記における必要な棒の数と対応している）
制約
2 <= N <= 10^4
方針
ある数字の組み合わせで整数を作る場合、大きい数字が上の桁にあるようにするとよいので、大きい数字から使用してゆくと仮定してよい。（※）
下記のDPを考える。
dp[i][j]: 残りコストがiで使用した最大の数字がjであるとき、その時点で作れる整数の最大値
DPの遷移は少し複雑だが、下記のようにあらわせる。
dp[i][k] = max(dp[i][k], dp[i+B[k]][j] * 10 + k)
B[k]は数字kを作るときのコストとする。
ループはi, k, jの3重ループで、下記のような意味合いを持つ。
i:残りコスト
j:これまでに使った数字の最大値
k:次に使う数字 これは（※）の仮定よりj以下
最初はどの数字から始めてもよいので、dp[N][0] = ... = dp[N][9] = 0とした。
サンプルケース1の遷移はざっくり下記の通り。
dp[17][7] = dp[20][7] * 10 + 7 = 7 ←これ以降は7以下の数字しか後につかない
dp[16][4] = dp[20][4] * 10 + 4 = 4 ←これ以降は4以下の数字しか後につかない（以下記載しない）
dp[15][3] = dp[20][3] * 10 + 3 = 3
dp[14][7] = dp[17][7] * 10 + 7 = 77
dp[13][7] = dp[17][7] * 10 + 4 = 74
dp[13][8] = dp[20][8] * 10 + 8 = 8
dp[12][4] = dp[16][4] * 10 + 4 = 44
...
感想
ABC118DはPythonで通しました。「出力が 64 ビット整数型に収まらない場合があります。」という文言をみて、いよいよPythonかと思ったのですが、整数型じゃなくても行けたんですね。https://t.co/aEnumAUjlh
— misora192 (@misora192) 2019年2月16日
C++だとDP配列を文字列で持たせるとよさそう。
作成されうる整数をどのようにして網羅するかが重要で、
数字を大きい順に使用するという仮定を使うとうまくDPで表現できた。
解答
N, M = map(int, input().split()) A = list(map(int, input().split())) dp = [[-1 for i in range(10)] for j in range(N+1)] B = [0 for i in range(10)] C = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6] for i in range(10): if i in A: B[i] = C[i] for i in range(10): dp[N][i] = 0 for i in range(N, -1, -1): for j in range(10): for k in range(j+1): if B[k] > 0 and i+B[k] <= N: # print(i, j, k, i+B[k]) dp[i][k] = max(dp[i][k], dp[i+B[k]][j] * 10 + k) # print(dp) ans = 0 for i in range(10): ans = max(ans, dp[0][i]) print(ans)
