01 背包的二进制优化

也是在刷题的时候发现的，比如 hiho week 195。一眼看过去就是一个 0-1 背包问题，然后直接 DP 上了，当时觉得应该问题不大，结果最后只有 50%，一看数据，100% 的数据为 1E5 量，简单的 DP 的话复杂度为 O(MN)，这样复杂度估计是 1E10，这样肯定会 TLE。

然后一看，他的单个商品的全权值很低，都在 [1, 10] 之间，这样的话，最多有 100 种组合，所以极端情况下，每个商品都会有 1000 个同类。这样就有了二进制优化的余地。简单的说就是，将多个重复的商品进行优化。比如 p(w, v) 的商品有 10 个，那么，我们可以将其简化为，一个 p(1w, 1v)，一个 p(2w, 2v)，一个 p(4w, 4v)，最后剩下一个 p(3w, 3v)。

这样的话，就将数据量从 10 简化到了 4。于是乎，就可以将数据量减少一个数量级。所以，最后这题的代码：

using namespace std;
typedef pair<uint64_t, uint64_t> pii;
typedef pair<pii, uint64_t> ppiii;
typedef pair<pii, pii> ppiipii;
int main() {
  ios::sync_with_stdio(false);
  uint64_t n, m;
  cin >> n >> m;
  map<pii, uint64_t> _ticks;
  for (uint64_t i = 0; i < n; i++) {
    uint64_t w, p;
    cin >> w >> p;
    _ticks[pii(w, p)]++;
  }
  vector<pii> ticks;
  for (auto tick : _ticks) {
    uint64_t idx    = 0;
    uint64_t remain = tick.second;
    while (remain > 0) {
      uint64_t cur = pow(2, idx);
      idx++;
      if (remain >= cur) {
        ticks.push_back(pii(cur * tick.first.first, cur * tick.first.second));
      } else {
        ticks.push_back(
            pii(remain * tick.first.first, remain * tick.first.second));
        cur = remain;
      }
      remain = remain - cur;
    }
  }
  vector<vector<uint64_t>> DP(2, vector<uint64_t>(m + 1, 0));
  for (uint64_t i = ticks[0].first; i <= m; i++) {
    DP[0][i] = ticks[0].second;
  }
  for (uint64_t i = 1; i < (uint64_t)ticks.size(); i++) {
    uint64_t cur = i % 2;
    uint64_t pre = (i - 1) % 2;
    for (uint64_t j = 0; j < ticks[i].first; j++) {
      DP[cur][j] = DP[pre][j];
    }
    for (uint64_t j = ticks[i].first; j <= m; j++) {
      DP[cur][j] =
          max(DP[pre][j - ticks[i].first] + ticks[i].second, DP[pre][j]);
    }
  }
  cout << DP[(ticks.size() - 1) % 2][m] << endl;
  return 0;
}

最后这题 AC。