欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客网暑期ACM多校训练营(第二场)A run [简单计数dp]

程序员文章站 2023-12-23 09:36:16
...

                                                     A run

牛客网暑期ACM多校训练营(第二场)A run [简单计数dp]

题目:云秒钟可以走1米或者跑k米,但是不能连续两秒钟或者多秒钟跑k米,问走到牛客网暑期ACM多校训练营(第二场)A run [简单计数dp]区间的不同的方案数。

思路:简单的计数dp,下面是有关dp的状态以及状态转移方程,

状态:dp[i][j]表示第i米是通过走1米还是走k米得到的方案数;

状态转移方程: dp[i+1][0] += (dp[i][0]+dp[i][1]);

                          dp[i+k][1] += dp[i][0];

代码:

/*
*2018 nowcoder second round 
*A run
*
*题解:dp
*状态:dp[i][j]表示第i米是通过走1米还是走k米得到的;
*状态转移方程:
*               dp[i+1][0] += (dp[i][0]+dp[i][1]);
*               dp[i+k][1] += dp[i][0];
*/
#include<bits/stdc++.h>
#define ll long long
 
using namespace std;
const int maxn = 1e6+7;
const int mod = 1e9+7;
int q, k, l, r;
ll dp[maxn][2];
 
void init()
{
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
            dp[0][1] = 0;
            for(int i = 0; i < maxn-100000; i++)
            {
                dp[i+1][0] += (dp[i][0] + dp[i][1])%mod;
                dp[i+k][1] += dp[i][0]%mod;
            }
            for(int i = 0; i < maxn; i++) dp[i][0] += dp[i][1]%mod;
            for(int i = 1; i < maxn; i++) dp[i][0] += dp[i-1][0]%mod;
}
 
int main() {
    while(scanf("%d%d", &q, &k)!=EOF)
    {
        init();
        for(int i = 0; i < q; i++){
            scanf("%d%d", &l, &r);
            printf("%lld\n", (dp[r][0] - dp[l-1][0] + mod)%mod);
        }
                     
    }
    return 0;
}

 

上一篇:

下一篇: