【随机化贪心】【动态规划】【NOI2010】成长快乐

【问题描述】
Nemo是一条无忧无虑的小鱼，它的初始体重为w0。可爱的Nemo希望自己能够尽快地成长，因此需要吃尽量多的食物。Nemo最喜爱的食物是海里的小虾。
已知Nemo对食物的情况了解如下：大海里共有n只小虾，从1到n编号，其中编号为i的小虾的重量为wi。将大海看作一个X-Y坐标系，在0时刻编号为i的小虾所在的位置为(xi, yi)。小虾在大海中作匀速直线运动，其中编号为i的小虾的速度向量为(pi, qi)，即在时刻t，它的位置为
(xi+pi*t,yi+qi*t)
Nemo在0时刻的位置为(x0, y0)，它可以在海中随意移动，但速度不超过V。Nemo希望通过自己的努力，在T个单位时间内(含T时刻)吃到的小虾重量总和尽量大。当Nemo与某只小虾同时移动到同一个位置上，且小虾的重量小于Nemo当时的重量，则Nemo可以将该小虾吃掉。当Nemo吃掉重量为wi的小虾之后，它的体重将增加wi。注意，小虾不会吃Nemo，且小虾之间也不会自相残杀。
Nemo希望你来帮助它制定一个成长计划，使得它吃掉的小虾重量总和尽量大。
【输入格式】
该题为提交答案型试题，所有输入数据nemo1.in~nemo10.in已在试题目录下。
对于每个数据，输入文件中第一行为五个实数w0, V, T, x0, y0。分别表示Nemo的初始体重、最大移动速度、时间限制以及Nemo在0时刻的位置。
第二行为一个整数n，表示大海中小虾的只数。
接下来n行，每行5个实数，包括wi, xi, yi, pi, qi，分别表示编号为i的小虾的重量、在0时刻的位置和速度向量。
【输出格式】
针对给定的10 个输入文件nemo1.in~nemo10.in，你需要分别提交你的输出文件nemo1.out~nemo10.out。
输出文件第一行包含一个整数k。表示在你的成长计划中，Nemo将吃到k只小虾。
第二行包含一个实数w，表示在你的成长计划中，Nemo吃到的小虾的重量总和。
接下来k行，每行4个数t, x, y, s。表示在时刻t，Nemo在位置(x, y)处吃掉了编号为s的小虾。其中t, x, y为实数，s为整数。
为保证验证程序的精度，所有实数建议至少输出到小数点后6位。在验证程序中，两个实数绝对误差不超过10-4时，即视为相等。【样例输入】
5 1 6 0 0
1
5 2 2 0 0
【样例输出】
1
5
5 2 2 1【样例说明】
在这个样例中，Nemo在时刻5在位置(2, 2)吃掉了1号小虾。其实Nemo到达(2, 2)的时间可以更早，但题中仅要求速度不超过V即可。【评分方法】
对于每组数据，我们设置了9个评分参数a10,a9,…,a2。如果选手的输出不合法，则得零分。否则，设在你的方案中，Nemo体重的增加量为wuser，你的分数将会由下表给出：

如果有多项满足，则取满足条件中的最高得分。

通法：随机化贪心，并且加上各种优化。

先说计算出从A出发，追赶一个当前位置为B，以速度v移动的小虾所需时间的方法如下。

如图所示，根据余弦定理，有：

即：

也即：

只需要用求根公式求解即可（取两根中的较小正根）。

朴素的随机化贪心算法如下。

先将所有的小虾按体重从小到大排序。
每次将所有小虾按照单位时间的收益（增重比上时间）从大到小排序，
选取一个最优的小虾，或者以一定概率接受更差的小虾（并迭代进行，即再以一定概率接受更差的小虾），这个概率可以是0.5，或1/e。

优化1：贪心多次，取最小值；
优化2：对更差的解进行限制（如果太差就直接舍去）；
优化3：提高时间所占的比重（按增重比上时间的平方从大到小排序）；
优化4：引入模拟退火的思想，即使遇到非常差的解，仍然以一定概率接受它（这个概率跟温度有关，每贪心一次就按照一定规律降温（如将温度减半））。
加上这些优化基本上就可以得全分了。