题意简化

有 $n$ 件物品，每件重量 $w_i \le 300$，价值 $v_i \le 10^9$。
求容量为 $1..k$（$k \le 10^5$）的多重背包最大价值。

核心算法：分重量优化 + 决策单调性

1. 按重量分组

由于 $w_i \le 300$，只有 $300$ 种不同重量。
将物品按重量分组，每组内按价值降序排序（贪心选）。

2. 对每个重量单独处理

设当前处理重量为 $c$，有 $sz$ 个物品价值 $w[1..sz]$（前缀和）。

对于模 $c$ 的每个余数 $r$（$0 \le r < c$），独立处理：

• 只考虑容量 $j \equiv r \ (\text{mod}\ c)$
• 这些容量形成等差数列：$r, r+c, r+2c, \dots$

3. 转化为决策单调性优化

对于模 $c$ 的剩余类，问题是：

$$dp[j] = \max_{t \le \min(sz, j/c)} \{ dp[j-t\cdot c] + w[t] \} $$

这可以看作每个物品重量为1，价值为 $w[t]$ 的特殊完全背包，但物品数量有限。

关键观察：这个转移满足决策单调性： 如果对于容量 $j$，选择 $t$ 个物品最优，那么对于容量 $j+c$，选择 $\ge t$ 个物品最优。

4. 分治优化（slove函数）

代码用分治解决决策单调性：

• 区间 $[u,v]$ 对应容量范围
• 区间 $[l,r]$ 对应可能的决策范围
• 找到中间点 $mid$ 的最优决策 $p$
• 递归：$[u,mid-1]$ 的决策在 $[l,p]$，$[mid+1,v]$ 的决策在 $[p,r]$

复杂度：$O(m \log m)$ 对每个剩余类。

算法步骤

1. 输入与排序：

   • 读入 $n$ 个物品 $(w_i, v_i)$
   • 按重量升序，同重量按价值降序排序

2. 分组处理：

   for(i=1; i<=n; i=j) {  // 相同重量的物品
       if(a[i].x > m) break;  // 重量超过预算，跳过
       
       // 计算前缀和 w[1..sz]
       for(j=i; a[j].x==a[i].x; ++j)
           w[j-i+1] = w[j-i] + a[j].y;
       
       sz = j-i;  // 该重量的物品数量
       
       // 对每个余数独立处理
       for(k=0; k<a[i].x; ++k) {
           // 收集所有容量 j ≡ k (mod c)
           // 用分治优化计算 dp
       }
   }
   

3. 分治优化（slove函数）：

   • 找到中间容量 $mid$ 的最优决策
   • 递归处理左右两边

4. 输出答案：$dp[1..k]$

复杂度分析

• 排序：$O(n \log n)$
• 分组：$O(n)$
• 对每个重量 $c$：处理 $c$ 个剩余类
• 每个剩余类：$O(\frac{m}{c} \log \frac{m}{c})$
• 总复杂度：$O(\sum_{c=1}^{300} c \cdot \frac{m}{c} \log m) = O(300 m \log m)$
• 实际 $m=10^5$，$300m\log m \approx 5\times 10^7$，可过

关键优化

1. 重量分组

只有300种不同重量，大大减少状态数。

2. 余数分离

同余的容量独立处理，转化为序列问题。

3. 决策单调性

利用数学性质，用分治代替枚举决策。

4. 前缀和贪心

同重量物品按价值降序，选前 $t$ 个一定最优。

样例解释

输入：

4 9
2 8  (重量2，价值8)
1 1  (重量1，价值1)
3 4  (重量3，价值4)
5 100 (重量5，价值100)

处理过程：

1. 重量1：物品(1,1)
2. 重量2：物品(2,8)
3. 重量3：物品(3,4)
4. 重量5：物品(5,100)

结果：容量1..9的最大价值：

• 1元：选重量1 → 价值1
• 2元：选重量2 → 价值8
• 3元：重量1+2 → 9
• 4元：重量2+2 → 但只有一个重量2物品，所以还是9
• 5元：重量5 → 100
• 6元：重量5+1 → 101
• 7元：重量5+2 → 108
• 8元：重量5+3 → 104，但5+1+2=109更优
• 9元：重量5+2+2 → 但只有1个重量2，所以5+3+1=109

输出：1 8 9 9 100 101 108 109 109

代码特点

• 快读快写优化IO
• 结构体排序
• 分治决策单调性
• 模运算分离剩余类