[ACM] ZOJ 3725 Painting Storages (DP计数+组合)
Painting Storages
Time Limit: 2 Seconds Memory Limit: 65536 KB
There is a straight highway with N storages alongside it labeled by 1,2,3,...,N. Bob asks you to paint all storages with two colors: red and blue. Each storage will
be painted with exactly one color.
Bob has a requirement: there are at least M continuous storages (e.g. "2,3,4" are 3 continuous storages) to be painted with red. How many ways can you paint all storages under
Bob's requirement?
Input
There are multiple test cases.
Each test case consists a single line with two integers: N and M (0<N, M<=100,000).
Process to the end of input.
Output
One line for each case. Output the number of ways module 1000000007.
Sample Input
4 3
Sample Output
3
Author: ZHAO, Kui
Contest: ZOJ Monthly, June 2013
解题思路:
这道题和省赛上的一道非常像啊。
。
假设曾经做过,省赛的时候也不会没思路。
。。
这道题单纯用组合是不行的。。。
题意为:用红蓝两种颜色给N个仓库(标号1—N)涂色。要求至少有M个连续的仓库涂成红色,问一共能够的涂色方案。
结果模1000000007
dp[i] 为 前i个仓库满足至少M个连续仓库为红色的方法数。
那么dp[M]肯定为1。 dp[0,1,2,3,......M-1] 均为0.
在求dp[i]的时候,有两种情况
一。前i-1个仓库涂色已经符合题意,那么第i个仓库涂什么颜色都能够,有 dp[i] = 2*dp[i-1] ;(有可能超出范围,别忘了mod)
二。加上第i个仓库涂为红色才构成M个连续仓库为红色。那么 区间 [i-m+1, i]。为红色,第i-m个仓库肯定是蓝色并且从1到i-m-1个仓库肯定是不符合题意的涂色。所以用1到i-m-1的仓库的全部涂色方法 2^(i-m-1) 减去符合题意的方法数dp[i-m-1] 。所以方法数为2^(i-m-1)
- dp[i-m-1]
代码:
#include <iostream>
#include <string.h>
using namespace std;
const int mod=1000000007;
const int maxn=100005;
int power[maxn+1];
int dp[maxn];//前i个仓库满足m个仓库为红色的方法数
int n,m; void getPower()//预处理出2的多少次方
{
power[0]=1;
for(int i=1;i<=maxn;i++)
power[i]=power[i-1]*2%mod;
} int main()
{
getPower();
while(cin>>n>>m)
{
memset(dp,0,sizeof(dp));
dp[m]=1;
for(int i=m+1;i<=n;i++)
dp[i]=(dp[i-1]*2%mod+power[i-m-1]-dp[i-m-1])%mod;
cout<<dp[n]<<endl;
}
return 0;
}
最新文章
- JS原生基础终结篇 (帅哥)
- How to Install The Alpha Control Packages.
- npm install 出现UNABLE_TO_GET_ISSUER_CERT_LOCALLY
- 原创:C语言打开、下载、删除网页,统计网页字符个数
- 启动Eclipse后卡在 android sdk content loader 的解决办法
- jquery尺寸:宽度与高度
- java攻城狮之路(Android篇)--MP3 MP4、拍照、国际化、样式主题、图片移动和缩放
- vsftp配置参数
- 如何在 iOS 8 中使用 Swift 实现本地通知(上)
- Myeclipse8.5 svn插件安装两种方式
- ESSENTIAL ENGLISH SLANG
- 安装composer时,提示 /usr/bin/env: php: 没有那个文件或目录
- 【转】VUE 爬坑之旅-- 如何对公共JS,CSS进行统一管理,全局调用
- oc调用swift的打包.a / framework 不成功?!
- 2 Class类
- Windows Community Toolkit 3.0 - Gaze Interaction
- C#如何运行外部程序(打开可执行程序):ShellExcute和Process
- python关联eureka实现高并发
- php: Cannot send session cache limiter
- 数学集合:N Z Q R C