434. Chemists

http://acm.sgu.ru/problem.php?contest=0&problem=434
题意自己看>_<
首先,令A[i]=S[i]-D[i]。。那么题目的目的就是把所有A[i]变成0
可以发现。。对于和为0的t个数来说。。可以用t-1次完成倒水。。。
那么。。这个题目就变成了把n个数分成尽量多的部分。每个部分的和都是0。。
显然可以3^n的集合dp。。不过这显然是要TLE的。。
其实最关键的地方就在这里。。。
考虑任何一个数的序列。。比如a1,a2,a3,a4这样的。。如果只能把一些连续的分成一段。。那么显然是每当部分和为0的时候分一下最优。。。
那么问题就转化成了。。求一个最优的序列。。为0的部分和尽量多!
这是和很傻叉的。。可以dp在2^n解决。。。

3 thoughts on “434. Chemists

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>