T1：奇怪的银行
可以直接把 \(1, 6^p, 9^p\) 当做物品大小，跑一遍完全背包。时间复杂度为 \(\mathcal{O}(n\log n)\)
记 dp[i][j] 表示前 \(i\) 种面值恰好凑出 \(j\) 元的最少张数
转移：
\[dp[i][j] = \min(dp[i-1][j], dp[i][j-w_i]+1)
\]
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
int m;
cin >> m;
vector<int> w(1, 1);
for (int i = 6; i <= m; i *= 6) w.push_back(i);
for (int i = 9; i <= m; i *= 9) w.push_back(i);
int n = w.size();
const int INF = 1001001001;
vector<int> dp(m+1, INF);
dp[0] = 0;
rep(i, n) {
for (int j = w[i]; j <= m; ++j) {
chmin(dp[j], dp[j-w[i]]+1);
}
}
cout << dp[m] << '\n';
return 0;
}