牛客网 暑期ACM多校训练营（第二场）A.run-动态规划 or 递推？

牛客网暑期ACM多校训练营（第二场）

水博客。

A.run

题意就是一个人一秒可以走1步或者跑K步，不能连续跑2秒，他从0开始移动，移动到[L,R]的某一点就可以结束。问一共有多少种移动的方式。

个人感觉是带约束条件的超级楼梯问题。说是dp其实就是递推吧。只要连续的两秒不是跑的就可以。所以在已经跑了i步的时候，直接考虑最后一步是跑的还是走的就可以了。

所以公式就是dp[i]=dp[i-1]+dp[i-1-k];然后前缀和预处理一下，直接从L的for到R的就可以了。

反正乱七八糟就出来了。现在写题写的脑子都没了。

代码:

 //A

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<map>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 const ll mod=;

 ll dp[maxn],ans[maxn];

 void init(int k)

 {

     for(int i=;i<k;i++)

         dp[i]=;

     dp[k]=;

     for(int i=k+;i<maxn;i++)

         dp[i]=(dp[i-]+dp[i-k-])%mod;

     for(int i=;i<maxn;i++)

         ans[i]=(ans[i-]+dp[i])%mod;

 }

 int main()

 {

     int q,k;

     scanf("%d%d",&q,&k);

     init(k);

     while(q--){

         int l,r;

         scanf("%d%d",&l,&r);

         printf("%lld\n",(ans[r]-ans[l-]+mod)%mod);

     }

 }

Come on，BABY.