题目思路

如果没有这些限制，就是一个经典的爬楼梯问题，我们使用动态规划解决。状态$dp(i)$为:从山底走到第$i$层的所有可能方案数。

但是我们有$p,k$的限制，所以转移形如:

我们可以暴力的直接转移，得到$O(nm^2)$ 的 $dp$ 但是时间不允许，会超时。只能拿一部分分数。

优化

仔细观察这两个限制,发现他们都具有单调性，也就是某个点$i$能转移的点$j$一定能构成连续的一段。 所以可以使用前缀和优化$dp$

学习网址:https://blog.csdn.net/qq_51282224/article/details/122769892

使用这个技巧之前，需要预处理一个数组$le_i$ 代表我最远能够从哪里跨过来。这个数组我们使用双指针预处理。

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
ll dp[100005] , s[100005];
int a[100005] , le[100005];
int main()
{
    int n , p , k;
    cin >> n >> p >> k;
    for (int i = 1 ; i <= n ; i++){
        int m;
        cin >> m;
        for (int j = 1 ; j <= m ; j++)
            cin >> a[j];
        // 双指针:预处理每个点最远能从哪里开始转移
        int sumh = 0;
        for (int x  = 1 , y = 1 ; y <= m ; y++){
            sumh += a[y];
            while (sumh > p || y - x + 1 > k){
                sumh -= a[x++];
            }
            le[y] = x - 1;
        }
        // 动态规划 , s 是 dp的前缀和数组
        s[0] = dp[0] = 1;
        bool ok = true;
        for (int j = 1 ; j <= m ; j++){
            // 无法跨过目前的山，G
            if (le[j] == j){
                ok = false;
                break;
            }
            // 前缀和转移优化
            dp[j] = s[j - 1];
            if (le[j] != 0) dp[j] = (dp[j] - s[le[j] - 1] + mod) % mod;
            // 维护前缀和
            s[j] = (s[j - 1] + dp[j]) % mod;
        }
        // 输出答案
        if (ok) cout << dp[m] << endl;
        else cout << "0" << endl;
    }
    return 0;
}

python

dp = [0 for i in range (100000)]
s = [0 for i in range (100000)]
le = [0 for i in range (100000)]
mod = 1000000009
n , p , k = list (map(int , input().split()))
for i in range (n):
    a = list (map(int , input().split()))
    m = a[0]
    sh = 0
    x = 1
    y = 1
    #双指针:预处理每个点最远能从哪里开始转移
    while y <= m:
        sh += a[y]
        while sh > p or y - x + 1 > k:
            sh -= a[x]
            x += 1
        le[y] = x - 1
        y += 1
    # 动态规划 , s 是 dp的前缀和数组
    s[0] = dp[0] = 1
    ok = True 
    for j in range (1 , m + 1):
       	# 无法跨过目前的山，G
        if le[j] == j:
            ok = False
            break
        # 前缀和转移优化
        dp[j] = s[j - 1]
        if le[j] != 0:
            dp[j] = (dp[j] - s[le[j] - 1] + mod) % mod 
        # 维护前缀和
        s[j] = (s[j - 1] + dp[j]) % mod 
    if ok:
        print (dp[m])
    else:
        print (0)

题目内容

小红是一个热爱户外运动的人，他周末经常约朋友一起登山。华光林山清水秀，景色宜人，让他感到非常愉悦。他喜欢在登山的过程中欣赏美景，感受大自然的魅力。同时，他也喜欢挑战自己，尝试攀登更高的山峰。

小红登山时每一步可以选择向上爬一个台阶或者多个台阶，如果登山时选择的台阶不同，则为一种爬山方案。

小红想知道，华光林的每座山各有多少种不同的爬山方案(输出结果对 $10^9 +7$ 取模)。

输入描述

第一行，三个整数 $N$ 、 $P$ 和 $K$ 分别代表山的个数 $N$ ，小红一次最高能爬的高度 $P$ 以及小红一次最多能跨越的台阶数 $K$ 。

( $1 \le N \le 10$ ， $1 \le P\le 1,000$ ， $1 \le K \le 1,000$ )

接下来 $N$ 行，每行的第一个整数 $M_i$ 表示第 $i$ 座山一共有 $M_i$ 个台阶，接下来有 $M_i$ 个整数，分别表示每个台阶的高度 $H_j$

( $1 \le M_i \le 10,000, 1\le H_j \le 1,000$)。

输出描述

输出 $N$ 行，每行一个整数，表示第 $i$ 座山小红可以选择的登山方案数目。

样例

样例一：

输入

3 3 2
4 1 1 1 1
4 2 2 2 2
5 2 2 2 3 4

输出

5
1
0

备注

如果某一台阶 $H_j$ 的高度超过了小红次能爬的高度 $P$ ， 那小红就不会选择这爬座山， 登山方案数为 $0$ 。