题目地址:HDU 5000
这个题当时有过这种想法,就是所有满足的情况的属性和是一定的。但是不会求方案数。。(太弱。。。)而且当时也很不确定猜测是否正确。。所以就放下了。。。算是通过学习了下dp求方案数吧。
至于那个猜测,我也给不出证明,但是个人觉得是只有在和都是相等的时候,才可以通过某一个数的增减来始终保持至少有一个较大的,至少有一个较小的,而假如和不一样的话,就会产生其中一个会消灭另一个的情况。所以就转换成了和是多少的情况下方案数最大。很明显能够猜的出来是和的一半的时候(同样不会证明。。。看不出来也可以直接找最大值)。
代码如下:
#include
#include
#include
#include
#include
#include
#include
#include
#include