pku acm 1456 分析报告
MC重出江湖 继续被acm虐待
这次最先选择的是pku 1456，该题的大概意思就是做有限项选择使目标函数最大化。
首先想到的01背包问题，但是后来发现该题不具有马氏链特征
举例如果有输入数据4 50 2 10 1 20 2 30 1，若通过正向方式则在deadline 1之前的最优解为选择50 2，在deadline 2之前的最优解为30 1 50 2，若考虑顺序问题则在作出50 2的选择后无法选择30 1。逆向方式也有问题 就是选择过多 迭代规模过大
由于输入规模是n<=10000使用的动态规划的方式会使计算复杂度很高 容易超时
其次便是使用贪心算法，每次选择最大利润的选项放在尽量接近其deadline的位置。
开始的想法是正向，以时间递减的方式选择每个时间点的最大利润选项，明显是错误的
例如输入5 10 1 20 1 50 3 60 3 70 3则选择序列应该是20 1 70 3 60 3最优解为70 3 60 3 50 3
后来改为逆向 问题依旧
吃了几个wa后决定搜索资料 找到这篇文章
看来想法还是相近的也是使用贪心，关键在于该文作者首先将利润排序（这个我确实没有想过 呵呵）
而后由利润从高到低尽量放入 直到全部放满为止
该文比较难懂 配合下面的回复才算明白 作者使用了并查集的算法导致比较难看懂 同时效率提高
其实但就算法而言就是对已经排序的有序整数对 对其后项 查找可放入的位置 并放入 直至放满
并查集的作用就是加快这个寻找过程，当然简单的搜索办法也可以奏效，线段树的方法也被提到了。
总结下自己的问题
1 对于贪婪算法的认识表浅–只知道按照次序来 不知道按照大小来
2 对于数据结构的忽视导致了算法优化的困难
先到这里下次补充
追加1：
想了一下这道题如何通过线段树的数据结构做
假设对1-10的时间做如下划分
假设先选择100 9 则将节点[8,9]标记 而后选择90 10 标记[9,10]
这时选择80 10发现[8,10]已经被标记 则选择了[7,8]标记（最接近的空闲节点）
可以发现搜索次数较之直接搜索有所减少
Leave a Reply