YZOJ P2202 Legend VII – Ornament

时间限制：1000MS 内存限制：131072KB

难度：$5.0$

• 题目描述

• 输入格式

第一行有两个整数 $N$ 和 $Q$，表示商店有 $N$ 个装饰品，一共有 $Q$ 个询问。

第二行有 $N$ 对整数，每 $i$ 对整数 $p_i, b_i$ 表示第 $i$ 个装饰品的价格和好看度。

接下来 $Q$ 行，每行两个整数 $a, c$，分别描述 $Q$ 个询问。

• 输出格式

对于每个询问输出一行，一个整数表示最大好看度。

• 样例输入

• 样例输出

• 数据规模与约定

对于 $30\%$ 的数据，$N \leq 100, Q \leq 1000$ 。

对于 $100\%$ 的数据，$N \leq 1000, Q \leq 100000, 1 \leq a \leq N, c \leq 1000$ 。

 

 

 

---

 

 

 

按照惯例，这题可以用一种奇怪的做法卡过去：正反两遍背包，然后对于每个询问 $O(c)$ 查找答案。时间复杂度 $O(Qc \approx 10^8)$ ，数据比较水就卡过去了。

详见代码

 

 

 

---

但是我们必须思考正解而不是套算法！

首先，由于“删除”这个操作不是很好实现，所以把思维逆转过来，考虑“增加”这个操作。

接着，还发现一个性质：如果不选的物品 $a$ 在区间 $[l, r]$ 中，那么 $a$ 不是在 $[l, \lfloor\frac{l+r}{2}\rfloor]$ 中就是在 $[\lfloor\frac{l+r}{2}\rfloor+1, r]$ 中（废话）。这提示我们，可以用分治的思想把这个问题分成多个子问题来解决。

对于一个区间 $[l, r]$ ，如果 $a$ 在 $[l, \lfloor\frac{l+r}{2}\rfloor]$ 中，那么另一个区间 $[\lfloor\frac{l+r}{2}\rfloor+1, r]$ 中的物品都是可以选的，所以对这些物品做01背包，然后继续处理 $[l, \lfloor\frac{l+r}{2}\rfloor]$ ；若 $a$ 在 $[\lfloor\frac{l+r}{2}\rfloor+1, r]$ 中也是同样。

但是很明显，在分治的时候需要不选 $[l, r]$ 区间物品，其他物品都选时的动态规划 $f$ 数组作为初始状态，这样才能继续对这个区间进行规划和分割。同时必须在回溯的时候把这个数组还原。对于每次递归和回溯都重新对除了 $[l, r]$ 中的物品做一遍01背包代价是很大的，可以达到 $O(N^2c)$ 等于是退化了。

注意到分治的递归树最多只有 $log_{2}{N^2} \approx 19$ 层，所以可以直接把每一层的动态规划 $f$ 数组都存下来，在对这一层进行规划的时候，直接把上一层的 $f$ 当做初始状态即可。这样回溯的时候也不必考虑如何保存并还原 $f$ 数组了。

最后，当分治到 $l=r$ 时，这个 $a$ 元素也就被确定下来了，更新去掉 $a$ 的答案的 $f’$ 数组即可。

这样，时间复杂度就只有 $O(NclogN)$ 足以通过本题。