P1833 | Ficon's Paper

一道比较裸的多重背包和完全背包的杂交版。

分类讨论即可。

暴力

略。

二进制拆分优化。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100;

int getTime(string time) {
  int h, m;
  sscanf(time.c_str(), "%d:%d", &h, &m);
  return h * 60 + m;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string T1, T2;
  int n;
  cin >> T1 >> T2 >> n;
  int t = getTime(T2) - getTime(T1);
  vector<int> w(n + 1), v(n + 1), p(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> w[i] >> v[i] >> p[i];
  }
  for (int i = 1; i <= n; i++) {
    if (p[i] > 1) {
      int x = p[i] - 1;
      int k = 1;
      p[i] = 1;
      while (x > 0) {
        v.emplace_back(v[i] * min((1 << k), x));
        w.emplace_back(w[i] * min((1 << k), x));
        p.emplace_back(1);
        n++;
        x -= (1 << k);
        k++;
      }
    }
  }
  vector<int> dp(t + 1);
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    if (p[i] == 0) {
      for (int j = w[i]; j <= t; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
      }
    } else {
      for (int j = t; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
      }
    }
  }
  cout << dp[t] << endl;
  return 0;
}

时间复杂度： $O(\sum_{i = 1}^{N}\log p_{i}\cdot V)$

单调队列优化

单调队列本质上是维护一段滑动窗口内的最优值。

我们发现：

$f[j] = \max \{ f[j], f[j-w]+v, f[j-2w]+2v, \dots, f[j-c \cdot w] + c \cdot v \}$

当我们要在背包容量 $j$ 放入体积为 $v$ 的物品时，我们只会用到 $j-v, j-2v, j-3v \dots$ 这些状态。

所以可以按照对体积的余数可以分成若干组。

for (int d = 0; d < w[i]; d++) // w 是 weight，v 是 value
	for (int j = d; j < t; j += w[i]) { // t 是背包总容量
	}

对于每一组都可以表示为： $j = d + p \cdot w$

$f[d + p \cdot w] = \max_{0 \le k \le c} \{ f[d + (p-k) \cdot w] + k \cdot v \}$

枚举 $p$ ，同时维护一个单调队列，会发现有一个问题：

单调队列维护的是最优的状态，但是这里“最优”取决于当前状态与队列中每个状态的差值（假设 $5$ 从 $3$ 转移， $k = 2$ ，但是当前状态是 $6$ 时， $k = 3$ ）

假设队头（最优转移）暂时一直都是 q.front()=p=3，当求 p=4 时，dp[j] = dp[q.front()] + w，当 p=5 时，dp[j] = dp[q.front()] + 2 * w

所以需要做一些转化：

对于每个固定的 $p$ ，想要知道当前队列里，谁更优，谁更劣。

$f[d + p \cdot w] = \max_{0 \le k \le c} \{ f[d + (p-k) \cdot w] - (p-k) \cdot v + p \cdot v \}$

对于队列中已经存在的每个 $f[d + (p - k) \cdot w]$ ，都减去对应 $p - k$ 个 $v$ ，因为对于每一个固定的 $p$ ， $p \cdot v$ 都相当于是一个常量，所以我们只需要维护 $f[d + p \cdot w] - p \cdot v$ 的最大值即可。

下面的代码中 j / w[i 代表 p。

复杂度为 $O(NV)$

用滚动数组优化了一下空间复杂度。

想一想，为什么不能通过倒序枚举优化空间？

vector<int> dp(t + 1), ans(t + 1);
for (int i = 1; i <= n; i++) {
  if (p[i] == 0) {
	for (int j = w[i]; j <= t; j++)
	  dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  } else {
	for (int d = 0; d < w[i]; d++) {
	  deque<int> q;
	  for (int j = d; j <= t; j += w[i]) {
		while (!q.empty() && (j - q.front()) / w[i] > p[i])
		  q.pop_front();
		while (!q.empty() && dp[q.back()] - q.back() / w[i] * v[i] <
								 dp[j] - j / w[i] * v[i])
		  q.pop_back();
		q.push_back(j);
		// dp[j] = dp[q.front()] + (j - q.front()) / w[i] * v[i];
		ans[j] = dp[q.front()] + (j - q.front()) / w[i] * v[i];
	  }
	  for (int j = (t - d) / w[i] * w[i] + d; j >= 0; j -= w[i]) {
		dp[j] = ans[j];
	  }
	}
  }
}
cout << dp[t] << endl;