以下摘要由GPT-4o生成:
题目一涉及计算长度为n且和为s的整数数列的可能方案数，这些数列的后一项总是比前一项增加a或减少b。目标是输出方案数模100000007的结果。题目二则要求在一个n×m的矩阵中统计小明从左上角到右下角的不同路径方案，条件是他必须恰好获取k件宝贝，而每格的宝贝价值需超过他手中的任何宝贝。最终结果也需对1000000007取模。这两个问题都涉及动态规划的应用与分析。

题目一

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为 nn 和为 ss 而且后一项总是比前一项增加 aa 或者减少 bb 的整数数列可能有多少种呢？

输入格式

共一行，包含四个整数 n,s,a,bn,s,a,b，含义如前面所述。

输出格式

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 100000007100000007 的余数。

数据范围

1
2
3
1≤n≤10001≤n≤1000,
−109≤s≤109−109≤s≤109,
1≤a,b≤106

分析

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//f[i][j]表示前i项的总和s 模n的余数为j的所有组合的集合
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, MOD = 100000007;
int f[N][N];
int get_mod(int a, int b){//取正数模
    return (a % b + b) % b;
}


int main(){
    int n, s, a, b;
    cin >> n >> s >> a >> b;
    f[0][0] = 1;
    for(int i = 1; i < n; i++)
        for(int j = 0; j < n; j++){//j的取值为模n的取值，即 0 -> n - 1；
            f[i][j] = (f[i - 1][get_mod(j - a * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)])%MOD;
        }
    cout << f[n - 1][get_mod(s, n)] << endl;
    return 0;
}

题目二

X 国王有一个地宫宝库，是 n×m个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式

第一行 33 个整数，n,m,k，含义见题目描述。

接下来 n 行，每行有 m 个整数 CiCi 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 k 个宝贝的行动方案数。

该数字可能很大，输出它对 * 1000000007 * 取模的结果。

数据范围

1
2
3
4
1≤n,m≤501≤n,m≤50,
1≤k≤121≤k≤12,
0≤Ci≤12

解法

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N = 55, MOD = 1000000007;
int f[N][N][13][14];
//f[i][j][k][c]表示从开始走到(i, j)取宝贝，当前路径价格为c的路径数;
//如果到(i, j)刚好取得宝贝数为k,则记录;
int w[N][N];
int m, k, n;

int main (){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> w[i][j];
            w[i][j]++;//有n*m个格子的宝贝价格;
        }
    }
    f[1][1][1][w[1][1]] = 1;//第一个
    f[1][1][0][0] = 1;//不取

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == 1 && j == 1) continue;//第一个已经枚举过;
            for(int u = 0; u <= k; u++){
                for(int v = 0; v <= 13; v++){
                    int &val = f[i][j][u][v];
                    val = (val + f[i - 1][j][u][v]) % MOD;// 从上方来且不取当前
                    val = (val + f[i][j - 1][u][v]) % MOD;// 从左边来方来且不取当前
                    if(u > 0 && v == w[i][j]){
                        for(int c = 0; c < v; c++){
                            val = (val + f[i - 1][j][u - 1][c]) % MOD;
                            //递增序列长度,小于w[i][j]的前c个;
                            val = (val + f[i][j - 1][u - 1][c]) % MOD;
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    for(int i = 0; i <= 13; i++) res = (res + f[n][m][k][i])%MOD;
    cout << res;
    
    return 0;
}

图解

  • 闫氏dp分析法：