YZOJ P2202 Legend VII – Ornament

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

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注