111qqz的小窝

老年咸鱼冲锋!

hdu 1709 The Balance (母函数)

http://acm.hdu.edu.cn/showproblem.php?pid=1709
题意:有n个砝码,第i个的重量为w[i],问从1到sum(所有砝码的重量之和)那些重量无法称量。(所有质量都是整数)
思路:母函数。 一个砝码可以看做有三种状态,放,放左边(+),放右边(-)

需要注意的一点是放在右边(-)的时候,可能是j-w[i],也可能是w[i]-j

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz