题解

问题分析

我们有一个特殊的 0-1 背包问题：

• 物品数量 $N \leq 500000$
• 背包容量 $M \leq 10^{12}$
• 物品价值 $v_i$ 和质量 $m_i$ 都可达 $10^{12}$
• 关键性质：任意两个物品的质量有整除关系

关键观察

1. 整除关系的结构：

   • 所有质量构成一个以最小质量为"根"的整除链
   • 存在最小质量 $m_{\min}$，使得所有 $m_i$ 都是 $m_{\min}$ 的倍数
   • 质量可以表示为：$m_{\min}, 2m_{\min}, 3m_{\min}, \dots$

2. 分层处理： 将物品按质量分组，质量间存在整除关系，可以分层处理。

算法步骤

1. 预处理和分组

• 找到所有不同的质量值，按大小排序
• 将物品按质量分组
• 对每组内的物品按价值密度 $\frac{v_i}{m_i}$ 降序排序

2. 分层动态规划

设 $m_1 < m_2 < \dots < m_k$ 是所有不同的质量值。

状态设计： 由于 $M$ 很大，不能直接开数组。我们利用质量间的倍数关系：

• 对于质量 $m_i$，只考虑模 $m_i$ 的余数类
• 用 map 或类似结构存储关键状态

状态转移： 对于第 $i$ 层（质量 $m_i$）：

• 对于每个可能的余数 $r$（$0 \leq r < m_i$）
• 考虑选择 $t$ 个当前层的物品（$t \geq 0$）
• 转移：$dp[r + t \cdot m_i] = \max(dp[r + t \cdot m_i], dp[r] + \text{前缀和价值}[t])$

3. 单调队列优化

对于每个余数类，使用单调队列优化多重背包：

for r in range(0, m_i):
    deque = collections.deque()
    for j in range(0, (M - r) // m_i + 1):
        current = dp[r + j * m_i] - j * base_value
        while deque and deque[-1][1] <= current:
            deque.pop()
        deque.append((j, current))
        # 移除超出数量限制的决策
        while deque and j - deque[0][0] > max_count:
            deque.popleft()
        dp[r + j * m_i] = deque[0][1] + j * base_value

4. 贪心剪枝

由于 $M$ 很大，但物品数量相对较少：

• 维护当前最优解的上界
• 当剩余容量很大时，可以直接选择所有高价值密度物品
• 使用价值密度贪心作为上界进行剪枝

复杂度分析

• 分组排序：$O(N \log N)$
• 分层DP：每层复杂度 $O(\text{该层物品数} \times \log M)$
• 总复杂度：$O(N \log M)$

样例验证

对于样例：

6 10
1 1
5 2  
200 6
9 2
6 2
100 1

分组：

• 质量1: [(1,1), (100,1)] → 按密度排序：[(100,1), (1,1)]
• 质量2: [(5,2), (9,2), (6,2)] → 按密度排序：[(9,2), (6,2), (5,2)]
• 质量6: [(200,6)]

分层处理：

1. 处理质量1：选择 (100,1) 和 (1,1)，总质量2，价值101
2. 处理质量2：在剩余容量8中，选择密度最高的 (9,2) 和 (6,2)，总质量4，价值16
3. 处理质量6：剩余容量4，无法选择 (200,6)
4. 调整：放弃部分质量2的物品，选择质量6的物品

最终最优解：质量1全选(2)+质量6(6)+部分质量2(2) = 总质量10，价值101+200+9=310

实现细节

1. 大整数处理：使用64位整数
2. 状态存储：使用 unordered_map 或类似结构，只存储可达状态
3. 剪枝优化：
   • 价值上界剪枝
   • 容量可行性剪枝
4. 特殊情况处理：
   • 所有质量相等：退化为标准背包
   • 只有两种质量：分别处理

代码框架

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

ll take_photos(int N, ll M, vector<pair<ll, ll>>& items) {
    // 1. 分组和排序
    map<ll, vector<ll>> groups;
    for (auto& [v, m] : items) {
        groups[m].push_back(v);
    }
    
    // 2. 每组按价值密度排序
    for (auto& [m, vals] : groups) {
        sort(vals.begin(), vals.end(), [m](ll a, ll b) {
            return a * m > b * m; // 按价值密度降序
        });
    }
    
    // 3. 分层DP
    map<ll, ll> dp;
    dp[0] = 0;
    
    for (auto& [m, vals] : groups) {
        map<ll, ll> new_dp = dp;
        
        // 对每个余数类使用单调队列优化
        for (ll r = 0; r < m; r++) {
            // 单调队列优化实现...
        }
        
        dp = move(new_dp);
    }
    
    // 4. 找最大值
    ll ans = 0;
    for (auto& [mass, value] : dp) {
        if (mass <= M) {
            ans = max(ans, value);
        }
    }
    return ans;
}

总结

本题的关键在于利用质量间的整除关系进行分层处理，结合单调队列优化和贪心剪枝，在超大容量下高效求解背包问题。通过数学性质将问题结构化，避免了直接处理超大状态空间。