题目：CF474D Flowers

传送门

DP？递推？

首先可以很快看出这是一道 DP 的题目，但与其说是 DP，还不如说是递推。

大家还记得刚学递推时教练肯定讲过的一道经典例题吗？就是爬楼梯，一个有 $n$ 阶的楼梯，一个人爬上去，每次可以爬一阶也可以爬两阶，问有多少种爬法？其实这道题也是一样的，只不过把 $2$ 换成了 $k$ 而已。

于是我们开始分析，定义 $dp[i]$ 为吃 $i$ 个蛋糕的吃法总数。

很容易看出，如果 $i<k$，就不可以一口气吃掉，只能一个一个吃，方法为 $1$ 种。

如果 $i==k$，就既可以一个一个吃掉，也可以一口气全部吃完，方法为 $2$ 种。

如果 $i>k$，就有两种吃法，既可以先吃 $i-1$ 个，然后再吃一个，也可以先吃 $i-k$ 个，再吃 $k$ 个。方法为 $dp[i-1]+dp[i-k]$ 种。

最后记得要开 long long，而且要一边加一边模 $1000000007$。

核心代码：

1
2
3
4
5
6
7
8
if(dp[i])continue;
if(i<k)
    dp[i]=1;
else if(i==k)
    dp[i]=2;
else
    dp[i]=(dp[i-1]+dp[i-k])%1000000007;
sum[i]=(sum[i-1]+dp[i])%1000000007;

因为一组数据只有一个 $k$，但是有很多组关于这个 $k$ 的测试点，所以可以用一个前缀和数组统计 $dp_1\sim dp_i$ 的和，然后根据题目中 $mod\ 1000000007$。

玄学优化

其实这个优化也不难想到。既然一组数据中只会有一个 $k$，那么说明不管怎么算，$dp[i]$ 的值算出来都是相等的。那么可以判断一下当前出现的最大 $x_2$，如果一组输入的 $x_2$ 值小于最大值，就说明 $dp[x_2]$ 已经计算过，直接输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,k,x1,x2,Max=1;
ll dp[100005],sum[100005];
int main(){
    scanf("%d %d",&t,&k);
    while(t--){
        scanf("%d %d",&x1,&x2);
        if(Max>=x2){ //优化：判断x2和max（x2）的大小
            printf("%lld\n",(sum[x2]-sum[x1-1])%1000000007);
            continue;//直接跳过
        }
        for(int i=Max;i<=x2;i++){//只计算没计算过的
            if(dp[i])continue;
            if(i<k)
                dp[i]=1;
            else if(i==k)
                dp[i]=2;
            else
                dp[i]=(dp[i-1]+dp[i-k])%1000000007;
            sum[i]=(sum[i-1]+dp[i])%1000000007;
        }
        printf("%lld\n",(sum[x2]-sum[x1-1])%1000000007);
        Max=x2;//更新Max的值
    }
    return 0;
}

究竟是什么地方错了？

然后你交上去发现WA了！

这也就是一个本蒟蒻在做题时犯的错误。

一般要取余的题都是一边计算一边取模，所以可能会造成dp数组中前面的值大于后面的值的情况。在最终计算 $x_1\sim x_2$ 的时候做的减法运算可能是负数，负数取模就出事了。

那如何解决呢？其实很简单，只需要在取模之前再加上一个 $1000000007$ 就可以了。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,k,x1,x2,Max=1;
ll dp[100005],sum[100005];
int main(){
    scanf("%d %d",&t,&k);
    while(t--){
        scanf("%d %d",&x1,&x2);
        if(Max>=x2){
            printf("%lld\n",(sum[x2]-sum[x1-1]+1000000007)%1000000007);
            continue;
        }
        for(int i=Max;i<=x2;i++){
            if(dp[i])continue;
            if(i<k)
                dp[i]=1;
            else if(i==k)
                dp[i]=2;
            else
                dp[i]=(dp[i-1]+dp[i-k])%1000000007;
            sum[i]=(sum[i-1]+dp[i])%1000000007;
        }
        printf("%lld\n",(sum[x2]-sum[x1-1]+1000000007)%1000000007);
        Max=x2;
    }
    return 0;
}

终于A了！www