USACO笔记(不定期更新)

Posted on 2009-09-13 15:52 hyf 阅读(349) 评论(0)  编辑 收藏 引用 所属分类: OI
    虽然USACO已刷完,但最近遇到一些相似问题依然频频出错,故在此记下一些笔记。

09-09-13
    usaco4.2有一道工件安排的题,大概题意是n个工件需要进行处理,必须先进行操作A然后是操作B,有m1台A机器和m2台B机器,给出每台机器的操作时间,要求最先完成所有工件操作A的时间和最先完成所有操作的时间。
    问题1的解法是很明显的贪心,即每次选出能最快完成当前工件的机器,证明很简单,从i-1到i选择最优机器是明显的,只需说明最优的i-1的局面对i是可以得出i的最优答案的,如果i-1有非最优局面添加一个工件可以达到更优,那么添加新工件的位置会占去一个以前的最优解位置,而以前的工件就会放到对于当时并不最优的位置上去,不会比把现在工件放到此位置更优。
    问题2的解法是按问题1的方法求出一个工件完成时间序列,然后用A大的匹配B小的这样的顺序来匹配,找出一个最大值就是答案。这个问题证明的关键是这样匹配的解是否是合法的(如果是合法的那么正确性显然),我们可以把工件的操作看成是倒着的,即先操作B再操作A,那么把操作B的部分换成B的最优操作序列显然是合法的,因为这是A和B的操作都是合法且不会互相干扰,并且必定不会比以前的差(因为这分别是A和B的最优操作序列),那么答案就是这两个序列的最有配对,显然最大配最小这样的顺序可得到最优解。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理