题目要求的是从l到r的每个位置w,从0走到w的位置总数再全部加起来。
因为不能连续跑两次,也就是如果这次跑了,那上次一定是走。
但是这次如果是走,那上次可以是跑的也可以是走的。
详细思路见代码中注释:
#include<bits/stdc++.h> using namespace std; #define MOD 1000000007 #define N 100000 int q,k; int maxr = 0; int main() { scanf("%d%d",&q,&k); if(!q) return 0; int val[N][2];//存q个l和r //读取q个l和r for(int i=0;i<q;i++) { scanf("%d%d",&val[i][0],&val[i][1]); maxr = max(maxr,val[i][1]);//记录r的最大值,这样dp只要计算到r就可以了 } //[*]maxr还有这样一个作用,当k比maxr还大的时候,从l到r每个都只有一种情况,不需做dp也不需前缀和 if(k>maxr) { for(int i=0;i<q;i++) { printf("%d\n",val[i][1]-val[i][0]+1);//r-l+1 } return 0; } //dp[i][0]表示到位置i的方法数,且最后一步是走;dp[i][1]表示到位置i的方法数,且最后一步是跑 int dp[N][2]; dp[0][0] = dp[0][1] = 0; //从初始位置跑一次(k)也就到了k位置,在这之前都只能走不可能是跑到的 for(int i=0;i<k;i++) { dp[i][0] = 1; dp[i][1] = 0; } //第k位置可能是一步跑到的,也可能是一步步走过来的 dp[k][0] = 1; dp[k][1] = 1; //dp[i][0] = 上一步是走+上一步是跑 的方法数 //dp[i][1] = 上一步是走 的方法数 for(int i=k+1;i<=maxr;i++) { dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % MOD; dp[i][1] = dp[i-k][0]; } //最终要求的是(dp[i][0]+dp[i][1])使i从l到r求和,因为查询很多次,用前缀和 //这里为节省空间,不妨都加到dp[i][0]上去 for(int i=1;i<=maxr;i++) { dp[i][0] = (dp[i-1][0] + dp[i][0] + dp[i][1]) % MOD; } //对每个查询输出结果 for(int i=0;i<q;i++) { //利用前缀和sum计算从item(l)加到item(r)的值,为sum(r) - sum(l-1) int v = dp[val[i][1]][0]-dp[val[i][0]-1][0]; if(v>=0) printf("%d\n",v); else printf("%d\n",(v+MOD)%MOD); } return 0; } //GitHub求star:https://github.com/LauZyHou/Algorithm-To-Practice