Codeforces 474 D Flowers（DP）

题目链接：
Codeforces 474 D Flowers
题意：
有两种花可以吃，white花只能连续吃k个，red花不受限制，当吃a到b朵花时一共有多少种吃法？也就是：

a朵花时的吃法+(a+1）朵花时的吃法+…+b朵花时的吃法。

分析：
$用dp[i][0]和dp[i][1]分别表示吃第i朵花时是white和red的情况。$

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
const int MAX_N=100010;
const int mod=(int)(1e9+7); int T,k,a,b;
int dp[MAX_N][2],ans[MAX_N],sum[MAX_N]={
   0};inline void solve()
{for(int i=1;i<MAX_N;i++){if(i<k) dp[i][0]=0,dp[i][1]=1;else if(i==k) dp[i][0]=1,dp[i][1]=1;else{dp[i][0]=(dp[i-k][0]+dp[i-k][1])%mod; //ith eat white flowerdp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod; //ith eat red flower}ans[i]=(dp[i][0]+dp[i][1])%mod; //ith total wayssum[i]=(sum[i-1]+ans[i])%mod;   //from 1st to ith total ways}
}int main()
{scanf("%d%d",&T,&k);solve();while(T--){scanf("%d%d",&a,&b);printf("%d\n",(sum[b]-sum[a-1]+mod)%mod); // +mod just in case of the result of sum[b]-sum[a-1] is negative}return 0;
}