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://m.huajiangbk.com/newsview104370.html
| 上一篇: 数据库基础操作 |
下一篇: Wireshark搜索/查找字符 |
