NEFU OJ Problem 1489 青蛙赶路 题解【动态规划DP】

• Problem:G
• Time Limit:2000ms
• Memory Limit:65535K

Description

有一只青蛙，每秒选择走1米或跳m米，青蛙体力不足，所以不能连续两秒都在跳。
青蛙将移动到[l,r]之间，它想知道有多少种不同的方式来实现其目标。
两种方式是不同的，当且仅当它们移动不同的米或花费不同的秒，或者是在一秒钟内，其中一个走而另一个跳。

Input

第一行输入包含2个整数n和m,n是查询数。（n <= 100000,2 <= m <= 100000）
对于下n行，每行包含两个整数l和r.（1 <= l <= r <= 100000）

Output

对于每个查询，输出到达的方案数，最后是模1000000007的答案。

Sample Input

4 4
4 4
1 4
1 5
1 6

Sample Output

2
5
8
12

思路

由于不能连续跳两次，所以除最后一次可能的跳跃外，每次跳之后必定走1米，于是将跳+走看作一个操作。

所以目前只有两种操作

1. 走：前进\(1\)米
2. 跳+走：前进\(m+1\)米。

注意其实还有第三种操作，即在最后一步选择跳跃,如果采用这种策略则可以在\([l-m,r-m]\)区间跳跃来达到最后一步到终点的效果。因此除了\([l,r]\)区间的DP值外还需要加上\([l-m,r-m]\)区间的DP值

代码如下

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5+1, MOD = 1000000007;
ll dp[N], s[N];

int n, m;
ll Find(int x)
{
    if(x < 0)
        return 0;
    ll res = 0;
    if(dp[x] != -1)
        return dp[x];

    if(x-1 >= 0)
        res += Find(x-1);

    if(x - m - 1 >= 0)
        res += Find(x-m-1);

    res = res % MOD;
    return dp[x] = res;
}
int main()
{
    cin >> n >> m;
    memset(dp, -1, sizeof dp);

    dp[0] = 1;
    s[0] = 1;//这里我用了前缀和，好像没必要
    for (int i = 1; i < N; i ++)
    {
        s[i] = s[i-1] + Find(i);
        s[i] = s[i] % MOD;
    }
    for (int i = 0; i < n; i ++)
    {
        ll res = 0;
        int l,r;
        cin >> l >> r;
        //计算[L, R]区间
        res = s[r] - s[l-1];

        //处理端点值，计算[L-m, R-m]区间
        l = max(0, l-m);
        r = max(0, r-m);
        if(l == 0)
            res += s[r];
        else
            res += s[r] - s[l-1];
        res = res % MOD;

        cout << res << endl;
    }


    return 0;
}