zoj 3725
2024-08-26 22:09:04
题意：
n个格子排成一条直线，可以选择涂成红色或蓝色，问最少 m 个连续为红色的方案数。
解题思路：
应该是这次 ZOJ 月赛最水的一题，可惜还是没想到。。。
dp[i] 表示前 i 个最少 m 个连续为红色的方案数。
转移时，分类讨论：
1、前 i-1 个已经满足这个性质，那么，第 i 个随意涂色，方案数为 dp[i-1] * 2 。
2、前 i-1 个不满足这个性质，那么，要想成为方案，区间 [i-m+1,i] 必须涂成红色。并且，下标为 i-m 这个点必须是蓝色，否则就与 情况1 重复了。
而且正是由于这一点，只要剩下的区间 [1,i-m-1] 不满足这个性质，就能保证整个区间 [1,i-1] 不满足这个性质。方案数为 2^(i-m-1) - dp[i-m-1]。
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- const int N = 1e5 + 5;
- const int mod = 1e9 + 7;
- int dp[N],pow[N]={1};
- int main()
- {
- int n,m;
- for(int i=1;i<N;i++)
- pow[i] = pow[i-1] * 2 % mod;
- while(~scanf("%d%d",&n,&m))
- {
- memset(dp,0,sizeof(int)*m);
- dp[m] = 1;
- for(int i=m+1;i<=n;i++)
- dp[i] = ((dp[i-1] * 2 % mod + pow[i-m-1] - dp[i-m-1]) % mod + mod) % mod;
- printf("%d\n",dp[n]);
- }
- return 0;
- }
最新文章
- Hadoop_UDTF示例
- 只需一点小修改，HTC Vive画面会更清晰锐利
- Installing MySQL Server on CentOS
- chrome修改UserAgent，调试
- 复习IOS多线程知识
- Swift--基础(二)元组 断言 错误处理
- Selector、shape详解，注意这两种图像资源都以XML方式存放在drawable不带分辨率的文件夹中
- [K/3Cloud] 如何从被调用的动态表单界面返回数据
- angular.js之路由的选择
- HCTF
- C语言的字符串操作函数小结
- JS string 常用方法总结
- 【python小练】0012题
- Redis主从哨兵和集群搭建
- 给学习Linux系统小白的两三个建议
- django从请求到响应的过程深入讲解
- Spring框架的事务管理相关的类和API
- IntelliJ IDEA 2017版 快捷键CTRL + SHIFT + A无效如何调试(详细的开启idea自动make功能 )
- PHP输出javascript，alert中文乱码解决办法
- Datatable paging,Repeater with Paging