首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
lydsy1708专题
BZOJ 4976 [Lydsy1708月赛]宝石镶嵌
【题解】 我们设总共有m个二进制位出现过1,那么如果n-k≥m,显然所有的1都可以出现,那么答案就是把所有的数或起来。 如果n-k<m,那么因为k不超过100,ai不超过1e5,所以n不超过117,直接n*1e5的Dp即可。 Dp的方式也是多种多样,如果设f[i][j]表示前i个数字或出j最少需要几个数字,那么转移方程为f[i][j|a[i]]=min(f[i-1][j|a[i]]
阅读更多...