zoj 3725 Painting Storages

 

ZOJ Problem Set - 3725

Painting Storages

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There is a straight highway with N storages alongside it labeled by1,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

这道动态规划的题知道怎么做了会很简单主要分两种情况

1.前dp[i-1]个仓库成立,dp[i]就可以任意选择，dp[i]=d[i-1]*2;

2.前的dp[i-1]个仓库不成立，加上第i个刚好成立，则[i-m+1,i]必须染成红色，另外第i-m个就必须为蓝色，

与[i-m+1,i]不同所以就可以得出状态方程dp[i]=dp[i-1]*2+(i-m-1的全排列）-dp[i-m-1]

*************LHHHHHHH

               i-m             I

前i-m-1个必须不满足条件所以全排列减去dp[i-m-1]就得到了不成立的情况

 

#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
  
using namespace std;  
  
int N = 10005;  
 int mod = 100000007;  
  
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(dp));  
        dp[m] = 1;//m的时候为1只有一种情况，所以下面从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;  
}  

 

 

补充：软件开发 , C++ ,