SGU 366. Computer Game

http://acm.sgu.ru/problem.php?contest=0&problem=366
这题的意思就是每个东西有2个分量a和b,从N个东西里选K个东西,让这些东西的a分量之和A和b分量之和B,|A-B|最小,在此前提下A+B最大
N<=60000,K<=20,0<=a,b<=50
首先dp的话,要记录当前A-B为t的之后,A+B的最大值。。
暴力DP显然会挂。。优化了半天。。时间在SGU上居然第三: )
首先可以注意到对每个东西(a,b)可以用(a-b,a+b)来表示它,而由于最多选K个东西,所以当相同a-b的东西超过K个的时候。。显然除了a+b最大的那K个之外就没用了。。
所以总过最多也只有20*100=2000个东西。。
然后就差不多了。。Dp一下就可以了。。

2 thoughts on “SGU 366. Computer Game

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>