文章目录

CF1428G2 Lucky Numbers (Hard Version) 做题笔记

发布于

题意

给定 $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#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/

暂无评论

发表评论