题解

问题分析

我们需要选择一些购物优惠和单独购买的商品，使得：

• 每个商品至少被获得一次
• 总费用最小

每个购物优惠提供四个可能的矩形区域选择，每个区域包含以 $(a_i,b_i)$ 为原点的某个象限内的所有商品。

关键观察

1. 区域独立性：每个优惠的四个区域是互斥的，我们只能选择其中一个区域。

2. 覆盖的单调性：如果一个商品被某个优惠的某个区域覆盖，那么所有在该区域内的商品都会被覆盖。

3. 坐标离散化：由于坐标范围很大但实际点不多，可以离散化坐标来简化处理。

算法思路

对于小数据（N ≤ 70, M ≤ 70）

使用状态压缩动态规划：

状态设计：

• $dp[mask]$：覆盖商品集合 $mask$ 的最小费用
• $mask$ 是位掩码，第 $j$ 位表示商品 $j$ 是否被覆盖

初始化：

• $dp[0] = 0$
• 其他状态初始化为无穷大

状态转移：

1. 单独购买商品：

   $$dp[mask] = \min(dp[mask], dp[mask \setminus \{j\}] + p_j) $$

2. 使用购物优惠： 对于每个优惠 $i$ 和每个区域 $q \in \{1,2,3,4\}$：

   $$dp[mask] = \min(dp[mask], dp[mask \setminus S_{i,q}] + c_i) $$

   其中 $S_{i,q}$ 是优惠 $i$ 的区域 $q$ 覆盖的商品集合

最终答案：$dp[(1 << M) - 1]$

预处理覆盖关系

对于每个优惠 $i$ 和每个区域 $q$，预处理覆盖的商品集合：

def get_covered_items(i, q, items):
    a, b = deals[i]
    covered = 0
    for j, (x, y, p) in enumerate(items):
        if q == 1 and x <= a and y <= b:
            covered |= (1 << j)
        elif q == 2 and x <= a and y >= b:
            covered |= (1 << j)
        elif q == 3 and x >= a and y <= b:
            covered |= (1 << j)
        elif q == 4 and x >= a and y >= b:
            covered |= (1 << j)
    return covered

复杂度分析

• 状态数：$2^M$
• 转移数：每个状态考虑 $M + 4N$ 种转移
• 总复杂度：$O(2^M \cdot (M + N))$
• 对于 $M \leq 20$：$2^{20} \approx 10^6$，可接受
• 对于 $M \leq 70$：$2^{70}$ 太大，需要优化

优化策略

对于 M 较大的情况

1. 区域支配关系：

   • 如果一个优惠的费用更低且覆盖范围包含另一个优惠，可以剔除被支配的优惠
   • 预处理时只保留非支配优惠

2. 商品分组：

   • 将商品按坐标分区，同一分区内的商品可能被相同的优惠覆盖
   • 减少实际需要考虑的商品数量

3. 费用流建模（对于中等数据）：

   • 源点 → 优惠节点（容量1，费用$c_i$）
   • 优惠节点 → 覆盖的商品节点（容量无穷，费用0）
   • 商品节点 → 汇点（容量1，费用$p_j$）
   • 求最小费用最大流

样例验证

输入：

2 4
1 1 3
3 3 13
0 0 2
0 2 5  
2 0 4
2 2 3

预处理覆盖关系：

• 优惠1（1,1,3）：
  • 区域1（x≤1,y≤1）：覆盖商品1
  • 区域2（x≤1,y≥1）：覆盖商品2
  • 区域3（x≥1,y≤1）：覆盖商品3
  • 区域4（x≥1,y≥1）：覆盖商品4

DP过程：

• 初始：dp[0000]=0
• 使用优惠1区域2：dp[0100]=3
• 单独购买其他商品：dp[1111]=3+2+4+3=12

最终答案：12

实现细节

1. 位运算技巧：使用位掩码表示商品集合
2. 无穷大设置：使用足够大的值，如 $10^{18}$
3. 内存优化：使用滚动数组或按大小顺序处理状态

总结

本题的核心在于：

1. 将几何覆盖问题转化为集合覆盖问题
2. 利用状态压缩DP处理小规模实例
3. 对于大规模实例，需要结合几何性质和优化技巧

通过合理的状态设计和预处理，可以在可接受的时间内解决小数据规模的问题。对于更大规模，需要更高级的算法技巧。