ABC118 D

問題

動的計画法を使う。

dpn配列に文字列の長さ、dp配列に文字列を格納する。配列の長さはマッチ棒の個数。

dpnを0から順番に調べ、初期値(-1)ではなく、追加したマッチ棒の個数の地点の長さが

①追加したい個所と同じ

・追加したい個所に、追加したい個所と新たな文字列のうち、大きいほうを格納

②追加したい個所より長い

・dpnを更新

・追加したい個所に、新たな文字列を格納

最終的にdp[n]が答え。

mi = {"1": 2, "2": 5, "3": 5, "4": 4, "5": 5, "6": 6, "7": 3, "8": 7, "9": 6}
n, m = map(int, input().split())
A = input().split()
dpn = [0] + [-1] * 10010
dp = [""] * 10010
for i in range(n):
    for a in A:
        if dpn[i] != -1:
            cnt = dpn[i] + 1
            if dpn[i + mi[a]] < cnt:
                dpn[i + mi[a]] = cnt
                dp[i + mi[a]] = max(a + dp[i], dp[i] + a)
            elif dpn[i + mi[a]] == cnt:
                dp[i + mi[a]] = max(dp[i + mi[a]], a + dp[i], dp[i] + a)
print(dp[n])