题意
给定 $k, F_0, F_1, F_2, F_3, F_4, F_5$。
你要把一个位数最多 $5$ 位的数 $n$，拆成 $k$ 个数的和，对 $k$ 个数中的每一个数的第 $i$ 位是 $3$ 的 $u$
倍的话就会获得 $u \times F_i$ 的价值。一个方案的价值为所有价值之和。你要让价值最大，求最大价值。
多组询问 $Q$ 次。
$1 \leq n \leq 10^6, 1 \leq Q \leq 10^5$
题解
每一位最多只有一个数不是 $3$ 的倍数，调整法证明。把不是 $3, 6, 9$ 的都放到最后一个数上，前 $k$ 个数就可以直接做多重背包求。
转化为背包大小为 $n$，每个物品重 $3 \times 10^i$，价值为 $F_i$，个数 $3 \cdot (k − 1)$ 个。然后用分组背包把后一个数的每一位加进去 $0 \to 9$ 都能选，但是只有 $3, 6, 9$ 才有贡献。
使用二进制拆分，时间复杂度 $\mathcal O(n \log k + Q)$。
代码
// By rbtree (https://rbtr.ee)
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define ra _Read()
using tp = long long;
tp _Read();
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp Hat_N = 1e6, pow3[] = {3, 30, 300, 3000, 30000, 300000};
array<tp, Hat_N + 3> f;
void update(tp c, tp v) {
for (tp i = Hat_N; i >= c; --i) {
f[i] = max(f[i], f[i - c] + v);
}
}
namespace __SOL__ {
signed main() {
tp n = ra * 3 - 3;
array<tp, 6> a;
for (tp i : {0, 1, 2, 3, 4, 5}) {
a[i] = ra;
}
for (tp i = 0; i < Hat_N; ++i) {
for (tp j = -1, k = i; k; k /= 10) {
f[i] += (!(k % 10 % 3)) * (k % 10) / 3 * a[++j];
}
}
for (tp i : {0, 1, 2, 3, 4, 5}) {
tp hat = min(n, Hat_N / pow3[i]);
for (tp j = 1; j < hat; j <<= 1) {
hat -= j;
update(pow3[i] * j, a[i] * j);
}
update(pow3[i] * hat, a[i] * hat);
}
for (n = ra; n--; printf("%lld\n", f[ra])) {
}
return 0;
}
} // namespace __SOL__
signed main() {
tp __MTCS__ = ::__MTCS__ ? ra : 1;
while (__MTCS__--) {
__SOL__::main();
}
return EXIT_SUCCESS;
}
tp _Read() {
bool __neg(0);
char __c(getchar());
tp __val(0);
for (; __c < 48 || __c > 57; __c = getchar()) {
__neg = __c == 45;
}
for (; __c > 47 && __c < 58; __c = getchar()) {
__val = __val * 10 + (__c & 15);
}
return __neg ? ~__val + 1 : __val;
}
/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/