1700*D. Flowers（DP&&前缀和&&预处理打表）

Problem - 474D - Codeforces

题意：

        有白花和红花两种，把 x 朵花排成一排，要求白花必须连续 k 个一块放置，则有 cnt 种情况。给出 a 和 b，计算a到b之间的 x 对应的 cnt 总和，并且对1e9+7取模。

解析：

        考虑DP。

        当数量 x 小于 k 的时候，只能全部放置红花，只有一种情况。

        当数量 x 等于 k 的时候，则为两种情况，多了一种 x 朵花都为白花的情况（要求必须 k 朵连续放置）

        当数量 x 大于 k 的时候，如果最新的一朵花我们放置红色，则其情况数量等于前一朵的情况数量。如果如果最新的一朵花我们放置白色，则连续 k 朵都为白色，则情况数量等于 x-k 的情况。

所以状态转移方程为 dp[ i ] = dp[ i-1 ]+dp[ i-k ]，i>k

        综上所述，状态转移方程为

                                      dp[ i ] = 1，i>=1 && i<k

                                      dp[ i ] = 2，i==k

                                      dp[ i ] = dp[ i-1 ]+dp[ i-k ]，i>k

        并且每次询问数据范围都为1e5，所以预处理前缀和。

        注意，因为每次都取模mod，可能导致最后答案小于 0 的情况，所以此时需要加一个mod。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e5+5,mod=1e9+7;

int t,k,dp[N],sum[N];

signed main(){

scanf("%lld%lld",&t,&k);

dp[1]=1;

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

dp[i]=1;

sum[i]=sum[i-1]+1;

}

dp[k]+=1;

sum[k]+=1;

for(int i=k+1;i<=1e5;i++){

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

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

}

while(t--){

int a,b;

scanf("%lld%lld",&a,&b);

printf("%lldn",(sum[b]-sum[a-1]+mod)%mod);

}

return 0;

}

相关知识

花期内花的数目【离散化+前缀和+差分】
REVERSO ONE ‘PRECIOUS FLOWERS’ 翻转系列珍稀花卉腕表 再添三款臻美新作
REVERSO ONE PRECIOUS FLOWERS翻转系列珍稀花卉腕表 集号吧
1700 #种植# ...
flowers的意思
leetcode 6044. 花期内花的数目 —（每日一难day1）
C++ 程序设计：花期内花的数目（LeetCode：2251）
只和花Only Flowers，花界
鲜切西兰花减压预处理的保鲜研究
Flowers 花

网址: 1700*D. Flowers（DP&&前缀和&&预处理打表） https://www.huajiangbk.com/newsview104370.html