状压dp做题笔记
2024-08-28 14:35:38
CodeChef Factorial to Square (分块决策)
Description
给定一个n,要求在[1,n]中删除一些数,并使剩下的数的乘积是一个完全平方数,同时要求乘积最大,求删除方案数.
\(n\leq 3000\)
Solution
首先要构造出最优解,考虑把所有数相乘,发现如果某个质因数出现的奇数次,那就必须要删掉一个.那么只用在[1,n]中把该质数删除即可,得到的就是乘积最大的完全平方数.
现在考虑构造方案. 要求被删除的数包含所有必删质因数,并且只能出现一次. 那么就可以抽象成一个01串.
现在把质因数分类处理,\(<\sqrt{n}\)的为一块,发现这样的质数只有13个,将这些数状压.
剩下的数就暴力枚举,对于一个质因数\(x\geq\sqrt{n}\),他的倍数不会超过\(\sqrt{n}\)个,那么对于每个x,枚举它的倍数做一次背包,同时预处理剩下的数的合法情况,进行转移,复杂度为\(O(n*2^{13})\).
CodeChef Organize The Wallet (dp构造与转移)
Description
一共有7种面值的纸币,现在给定一个长度为n的纸币排列序列,要求进行一些插入操作,使得序列每种面值都是排列在一起的.求最小移动步数.
\(n\leq 100000\)
Solution
- 插入操作的性质:如果把一张纸币拿出来,那么可以把它放到任意位置.
- 可以考虑枚举放置顺序
- 如果在当前状态要放的纸币种类和当前位置的纸币种类不同,那就一定要把这个纸币抽走.
- 如果相同,那就不移动
- 如果该数应该出现在前面,那就插入到前面.
- 转移方程大概为:
- \(chkmin(dp[i][j][k],dp[i-1][j][k]) (Col[i]=k)\)
- \(chkmin(dp[i][j][k],dp[i-1][j][k]+1) (Col[i]!=k,Col[i]\in j)\)
- \(chkmin(dp[i][j|Col[i]][Col[i]],dp[i-1][j][k]) (Col[i]\notin j)\)
- \(chkmin(dp[i][j][k],dp[i-1][j][k]+1)(Col[i]\notin j)\)
最新文章
- JFinal学习
- R语言拆分字符串
- Apache Shiro 使用手册(四)Realm 实现
- linux账户管理[转自vbird]
- 使用ab测试工具 进行并发测试
- 【转】Multithreaded Python Tutorial with the “Threadworms” Demo
- Java开发23中设计模式
- 【转】Visual Stdio VS 错误 error : 0xC00000FD: Stack overflow. 更改堆栈空间解决栈溢出问题
- 1755: [Usaco2005 qua]Bank Interest
- 2017Java技术预备作业1501黄学超
- POP3是收邮件的协议,SMTP是发邮件的协议,IMAP是一种邮箱通信协议。
- c++ 变量的存储类别
- jdk和cglib动态代理
- webpack代理解决跨域问题
- Android数据库大批量数据插入优化
- spring配置jax-ws
- docker网络之bridge
- BZOJ4276 : [ONTAK2015]Bajtman i Okrągły Robin
- 使用sys用户创建其他用户下的dblink
- jQuery插件制作方法详解
热门文章
- 【AI】【人工智能】【计算机】人工智能工程技术人员等职业信息公示
- 【AtCoder】AGC010
- 【AtCoder】ARC069
- SpringBoot或者SpringMVC 临时取消配置的视图页面的前后缀
- Codeforces 718A Efim and Strange Grade 程序分析
- Jmeter博文索引~基础知识和实践操作汇总
- .Net C# RSA签名和验签重写
- 怎样在Chrome浏览器上安装 Vue Devtools 扩展程序
- springboot由于bean加载顺序导致的问题
- 电脑无法上网,DNS出现fec0:0:0:ffff::1%1问题