题解 CF474D 【Flowers】

Tenshi · 2020-11-12 20:22:43 · 题解

关键点：dp

分析：

看到题面 “当蛋糕数量为x1到x2之间” 的描述，不难想到可以用前缀和刻画这一点，如下

int sum(int l,int r){
    return (s[r]-s[l-1]+mod)%mod;
}

接下来考虑蛋糕数量为x的时候有多少种吃法：

我们这样考察：x个蛋糕，如果采取办法1吃，那么会剩下x-1个蛋糕，采取方法2则会剩下x-k （这里x>=k，写代码时注意判断）个蛋糕。

记f(x)为吃x个蛋糕的方法数，我们有：

f(x)=f(x-1)+f(x-k) (x>=k)

这，便是dp题的核心：状态转移方程

核心代码如下，我们从x=1开始依次更新：

for(i=1;i<=maxn;i++){
        if(i>=k) f[i]=f[i-1]+f[i-k];
        else f[i]=f[i-1];
    }

其他补充：

记得初始化x=0的情况 f[0]=1

取模

结合前缀和处理

顺利AC~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007 
#define maxn 100001
ll t,k,i;
ll f[maxn];
ll s[maxn];
int sum(int l,int r){
    return (s[r]-s[l-1]+mod)%mod;
}
int main(){
    cin>>t>>k;
    f[0]=s[0]=1;
    f[1]=1;
    for(i=1;i<=maxn;i++){
        if(i>=k) f[i]=(f[i-1]+f[i-k])%mod;
        else f[i]=f[i-1]%mod;
        s[i]=(s[i-1]+f[i])%mod;
    }
    while (t--)
    {
        int l,r;
        cin>>l>>r;
        cout<<(sum(l,r)+mod)%mod<<endl;
    }

    return 0;
}