bndsoj0759 B. 2018-8-12noip模拟测验(二)-篮球比赛2

维护集合 \(S\),表示前i个数能拼出的数的集合。k最大只有20,所以 \(S\) 集合状压可以存下

\(dp[i][S]\) 表示前i个数,拼出的数的集合为状压的 \(S\) 时的方案数

现在要把 \(dp[i][S]\) 转移到 \(dp[i+1][S’]\) ,有转移方程 \(S’=S|S_{new}\&((1<<k)-1)\)

转移的同时维护01背包,处理出加入i+1这个数后能凑出的新的数的集合\(S_{new}\),即:

\(dp[i+1][S|(s<<x)\&((1<<k)-1)]+=dp[i][S]\),其中\(s\in S_{new}\)

答案就是\(\max\left\{dp[n][(1<<k)\&x]\right\}\),其中\(x\in \left[0,\left(1<<k\right)-1\right]\)

初状态有\(dp[0][\{0\}]=1\)

时间复杂度:\(O(n^2\cdot 2^n)\)

代码写出来了再补

发表评论

电子邮件地址不会被公开。 必填项已用*标注