P11229 [CSP-J 2024] 小木棍（官方数据）题解

haokee · 2024-11-07 17:25:52 · 题解

使用 dp，令 dp_i 表示为使用 i 根小木棍能够拼出的最小数（使用 string 存储），很容易写出时间复杂度为 \mathcal O(n^2) 的 dp（状态数量 \mathcal O(n)，但是 dp_i 的长度有 \mathcal O(n)），但是实际上严重卡不满，反而空间达到了 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 a[kMaxN], f[kMaxN], t, n;
string dp[kMaxN];

void pre() {
  for (int i = 1; i <= 1e5; i++) {
    // 从前面转移过来
    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]) {
        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;
}