一道 dp 题。
在 dp 之前，我们需要明确以下几个东西：
状态的表示，状态转移方程，边界条件跟答案的表示。
状态的表示
\(dp_i\) 表示恰好用完 \(i\) 根火柴能拼出来的最大数字。
状态转移方程
\[dp_i = \max\{j \times 10^{len(dp_{i-w_j})} + dp_{i-w_j}\}
\]
其中 \(len(n)\) 表示 \(n\) 的位数，\(w_i\) 表示拼出数字 \(i\) 所需的火柴数量。实际上这里是将 \(dp_{i-w_j}\) 拼在 \(j\) 后面。
边界条件
\[dp_i = 0
\]
答案的表示
\[dp_n
\]
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n, m;
ll w[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string dp[10005];
bool vis[10];
string strmax(string x, string y) {
if (x.size() > y.size()) return x;
if (x.size() < y.size()) return y;
for (int i = 0; i < x.size(); i++) {
if (x[i] < y[i]) return y;
if (y[i] < x[i]) return x;
}
}
ll sum(string s) {
ll res = 0;
for (int i = 0; i < s.size(); i++) res += w[s[i] - '0'];
return res;
}
int main() {
ios :: sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
ll x;
cin >> x;
vis[x] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 9; j++) {
if (vis[j] and i >= w[j] and sum(to_string(j) + dp[i - w[j]]) == i) dp[i] = strmax(dp[i], to_string(j) + dp[i - w[j]]);
}
}
cout << dp[n];
return 0;
}