递推DP(至少和至多之间的转换
题意:给你一个硬币,抛掷n次,问出现连续至少k个正面向上的情况有多少种。
转换成抛N次至多连续有N个减去抛N次至多连续有K-1个1的情况 dp[i][k]表示抛i次至多连续有k个1的情况数;
转移方程:i<=k的时候有dp[i][k]=dp[i-1][k]*2 因为因为dp[i][k]表示抛i次至多连续有k个 i<=k的时候不会出现非法的情况
i>k的时候 如果i-j到i-1都是1 那么i=1就不可行 所以dp[i][k]=dp[i-1][k]-i-j到i-1都是1的情况数
i-j到i-1都是1的情况数:试想第i-j-1个位置应该是什么呢.很明显应该是F.如果是H那就会出现非法状态了.那在第i-j-1之前的位置呢.无论H和F都可以,只要不出现连续的H个数大于j的非法状态即可,就是dp[i-j-2][j]。
即将i-1到i-j-1的数都看作是"确定的一个数"所以情况数是dp[i-j-2][k];
然后将i==k+1的时候特判
题意:有三个兵种R,G,P,选取N个排成一列,要求G至少有M个连续的,R至多有K个连续的,问有多少种排列方式。
dp[i][4]的1,2,3表示第i个放R,G,P时最多有x个连续的G和y个连续的R的情况
这样就转换成了求 sum(dp[n][i])x=M y=N的情况减去sum(dp[n][i])x=M y=K的情况
dp[i][3]因为对RG没有影响所以递推公式始终为
dp[i][3]=sum(dp[i-1][1],dp[i-1][2],dp[i-1][3]);
i<=y时
dp[i][1]=dp[i][3];//R
i==y+1时
dp[i][1]=dp[i][3]-1;
i>y+1时
dp[i][1]=dp[i][3]-dp[i-y-1][2]-dp[i-y-1][3];
i<=x时
dp[i][2]=dp[i][3];//G
i==x+1时
dp[i][2]=dp[i-1][1]+dp[i-1][3]+dp[i-1][2]-1(1~x全为G的情况)
i>x+1时
dp[i][2]=dp[i][3]-dp[i-x-1][1]-dp[i-x-1][3];
最新文章
- [mobile开发碎碎念]手机页面上显示PDF文件
- Android ListView实现不同item的方法和原理分析
- Windows安装包制作指南——Advanced Installer的使用
- Configuring Report Manager
- java jvm学习笔记十二(访问控制器的栈校验机制)
- 设计一个算法,输出从u到v的全部最短路径(採用邻接表存储)
- Ant工具
- docker 1.10.3 里php出现 curl 56错误码问题解决
- ajax请求webservice时抛出终止线程的异常
- nginx access log logrotate配置
- vs2013 中已经添加了引用,编译还是提示没有添加引用
- Redis学习-复制
- JavaScript创建按钮,实现数字自加1!!
- [android] android下创建一个sqlite数据库
- Swift 学习- 09 -- 枚举
- [mariadb]Windows Mariadb 10.2安装过程
- TFS 安装 扩展包
- 【BZOJ2281】[SDOI2011]黑白棋(博弈论,动态规划)
- LeetCode(31): 下一个排列
- angular中的$q服务实例
热门文章
- SAP EXCEL OLE常用方法和属性
- linux常用命令(13)tail命令
- appium+python+windows环境配置
- laravel 5.8 实现消息推送
- Spring MVC 根容器和子容器
- 【AMAD】django-filer -- 一个管理文件和图片的django app
- C# Tcp协议收发数据(TCPClient发,Socket收)
- 【Linux开发】linux设备驱动归纳总结(三):6.poll和sellct
- Oracle密码过期(the password has expired)
- Array of Doubled Pairs