链接:http://acm.hdu.edu.cn/showproblem.php?pid=6425
n个人去打羽毛球,其中a个人没球没拍,b个人只有拍,c个人只有球,d个人什么都有。现在规定只要有两个人有拍,一个人有球就能去打。问有多少种组合不能去打。
JLS给的解居然是个dp,惊了。
直接考虑有几种情况不能去打:球和拍都不够、球够拍不够、拍够球不够。
(a个白嫖哥去不去都无所谓,因此他们对答案的整体贡献是2a。)
球和拍都不够:分两种情况,完全没有拍和只有一个拍。第一种的贡献只有a出,第二种贡献从a和b里出。因此总体答案是2a+2a×C1b。
球够拍不够:这个贡献可以拆分成a和c、a和b、a和b和d里出。第一种(没有拍子)c类人随意去就可以(不能不去),贡献是2a×(2c−1)。第二种(只有一个拍子,b类人出拍子,c类人出球),贡献是2a×C1b×(2c−1)。第三种(只有一个拍子,d类人出拍子),贡献是2a×C1d×2c。
拍够球不够:只有b类人,且至少去2个,贡献是2a×C2b。
全加起来就完事了。
1 |
|
v1.5.2