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)\) 足以通过本题。