【NOIP模拟赛】篮球比赛2

2014年11月5日1,8061

    由于Czhou举行了众多NOIP模拟赛,也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进,并且球技不断精进。这引起了体育老师彩哥的注意,为了给校篮球队找到势均力敌的对手,彩哥找到了Czhou神,想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子,决定派出配合默契又不至于吊打校篮球队的阵容。

而机房神牛的能力值受到游戏时长,训练时长,个人基础值得影响,可能会不断变化。所以Czhou想根据神牛当天状态从中选出若干名选手,使他们的能力值和等于k。

Input: basketball2.in

    一行三个数n,k,l。表示机房有n个神牛,选出队员能力值和为k,每个神牛的能力最大值<=L且>=0。

Ouput:basketball2.out

    输出一个数,表示方案数,方案满足选出若干选手使能力和为k。因为答案比较大,最后模10^9+7

Sample.in

2 2 2

Sample.out

6

    样例说明:神牛的能力值可能为(0,2)(1,2)(1,1)(2,0)(2,1)(2,2),这样都可以选出一些数字使他们的能力值和为2。

    对于(0,2)表示第一只牛能力值为0,第二只牛能力为2

类似的

对于(1,2)选出2即满足要求。

对于(1,1)选出全部选手即满足要求。

所以(0,2)(1,1)都是满足要求的方案。

数据范围:

n,k<=20

0<=L<=10^9.

题解

暴力直接爆搜+背包

正解状压

排列组合以及其余的dp算法似乎都会涉及重复统计的问题

dp[i][state] 表示前i位,state的二进制每一位表示和为(1~k),1表示可以取到,0表示取不到,0<=state<(1<<K)-1

枚举第i+1个取的数 f[i][j]->f[i+1][(i|(i<<x)|(1<<(x-1)))&((1<<K)-1)]

这是一个2^n*n^2的dp,但是状压废状态比较多,剪掉废状态即可AC。。。

 

  • ffffff2016年3月3日 下午1:19 回复

    g

    #1