使用 dp，令 $dp_i$ 表示为使用 $i$ 根小木棍能够拼出的最小数（使用 string 存储），很容易写出时间复杂度为 $\mathcal O(n^2)$ 的 dp，但是实际上严重卡不满，反而空间达到了 800 M，导致 MLE。

为了解决这个问题，我们可以将不要的状态丢掉。不难发现 $dp_i$ 最多从 $dp_{i-9}$ 转移过来，因此我们直接将过时且不需要询问的状态存储丢弃，这样即可通过官方数据。

#include <iostream>
#include <string>
#include <ctime> 

using namespace std;

const int kMaxN = 1e5 + 5, kT[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; 

int p[kMaxN], a[kMaxN], f[kMaxN], t, n;
string dp[kMaxN];

void pre() {
  for (int i = 1; i <= 1e5; i++) {
    p[i] = -1;
    for (int j = 0; j <= 9; j++) {
      if (i - kT[j] < 0 || 
          i - kT[j] == 0 && !j || 
          i - kT[j] && dp[i - kT[j]].empty()) {
        continue;
      }
      string t = dp[i - kT[j]] + char(j + 48);
      if (dp[i].empty() || 
          t.size() < dp[i].size() || 
          t.size() == dp[i].size() && t < dp[i]) {
        p[i] = i - kT[j];
        dp[i] = t;
      }
    } 
    if (i > 10 && !f[i - 10]) {
      dp[i - 10].clear();
      dp[i - 10].shrink_to_fit();
    }
  } 
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> t;
  for (int i = 1; i <= t; i++) {
    cin >> a[i];
    f[a[i]] = 1;
  }
  pre();
  for (int i = 1; i <= t; i++) {
    cout << (dp[a[i]].empty() ? "-1" : dp[a[i]].c_str()) << '\n';
  }
  return 0;
} 

题解链接