AcWing 蓝桥杯AB组辅导课 03、数学与简单dp

举报
长路 发表于 2022/11/22 23:53:46 2022/11/22
2.1k+ 0 0
【摘要】 前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是300+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！目

@[toc]

前言

前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是300+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！

  • 目前是打算参加Java组，所以所有的题解都是Java。

本章节数学及简单dp的习题一览：包含所有题目的Java题解链接

image-20221002103640977

  • 例题的前三题是蓝桥杯关于数学内容；后三题是简单dp内容。
  • 习题则是蓝桥杯题，相对于例题是进行了一个扩展。

例题：

习题：

其中背包问题（算法基础课）、摘花生(提高课)、最长子序列(提高课)

一、数学

蓝桥杯中的数学更像脑筋急转弯，涉及到一些数学的模型。

  • 竞赛中的考察比较深的数学知识。

例题

例题1：AcWing 1205.买不到的数目【简单，蓝桥杯】

题目链接：1205. 买不到的数目

分析：若是不知道这个数学公式的话，只能通过先进行打表进行推举，或者按照思路2来进行从最大数往前进行推理。

解题：

暴力打表：暴力多组数据来最终去找规律

//包装中可能有的糖果数量n或m，求不能买到的糖果数量

import java.util.*;
import java.io.*;

class Main {
    
    private static int n, m;
    
    public static boolean dfs(int m, int p, int q){
        if (m == 0) return true;
        if (m >= p && dfs(m - p, p, q)) return true;
        if (m >= q && dfs(m - q, p, q)) return true;
        return false;
    }
    
    public static void main(String[] args)throws Exception{
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.valueOf(s[0]);
        m = Integer.valueOf(s[1]);
        int res = 0;
        for (int i = Math.max(n, m); i <= 1000; i++) {
            if (!dfs(i, n, m)) res = i;
        }
        System.out.printf("%d\n", res);
    }
}

image-20221002214823002

思路1：公式一条解决

最终解决，实际上只需要使用一条公式即可：(p-1)*(q-1)-1

//包装中可能有的糖果数量n或m，求不能买到的糖果数量

import java.util.*;
import java.io.*;

class Main {
    
    private static int n, m;
    
    public static void main(String[] args)throws Exception{
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.valueOf(s[0]);
        m = Integer.valueOf(s[1]);
        System.out.printf("%d\n", (n - 1) * (m - 1) - 1);
    }
}

image-20221002220526734

思路2：从大到小进行推举

学习博客：AcWing 1205. 最简洁代码+详解 

//包装中可能有的糖果数量n或m，求不能买到的糖果数量

import java.util.*;
import java.io.*;

class Main {
    
    private static int n, m;
    
    public static void main(String[] args)throws Exception{
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.valueOf(s[0]);
        m = Integer.valueOf(s[1]);
        //从最大的进行往前推
        int k = n * m;//解必然在n*m下
        while (k != 0) {
            int t = k;
            while (t % m != 0 && t - n > 0) t -= n;
            //此时t % m == 0 或者 t - n < 0
            //该条件：①t % m != 0，表示筛选得到t - n < 0情况。②k不满足% n  % m的情况
            if (t % m != 0 && k % n != 0 && k % m != 0) {
                System.out.printf("t = %d, m = %d, n = %d\n", t, m, n);
                System.out.printf("%d", k);
                break;
            }
            k--;
        }
    }
}

image-20221002220443703

例题2：蚂蚁感冒【简单，蓝桥杯】

题目链接：1211. 蚂蚁感冒

分析：讨论情况题

统计位置为第一个右边 右向左(<0)，统计位置为第一个左边 左向右(>0)

两只蚂蚁碰面（灵魂互换继续向各自方向向前，且都感染）

题解：

import java.util.*;
import java.io.*;

class Main {
    
    private static final int N = 55;
    private static int n;
    private static int[] arr = new int[N];
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        String[] s = cin.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(s[i]);
        }
        int rightToLeft = 0, leftToRight = 0;
        for (int i = 1; i < n; i++) {
            //统计位置为第一个右边    右向左(<0)
            if (Math.abs(arr[i]) > Math.abs(arr[0]) && arr[i] < 0) rightToLeft++;
            //统计位置为第一个左边    左向右(>0)
            if (Math.abs(arr[i]) < Math.abs(arr[0]) && arr[i] > 0) leftToRight++;
        }
        //情况1：左右的蚂蚁必感染
        //若是第一个蚂蚁向右 && 右边的蚂蚁向左的数量!=0
        //若是第一个蚂蚁向左 && 左边的蚂蚁向右的数量!=0
        //情况2：非情况1，此时感染蚂蚁的数量为1
        if (arr[0] > 0 && rightToLeft != 0 || arr[0] < 0 && leftToRight != 0) {
            System.out.printf("%d", leftToRight + rightToLeft + 1);
        }else {
            System.out.printf("%d", 1);
        }
    } 
}

image-20221003181750460

例题3：饮料换购【简单，蓝桥杯】

题目链接：1216. 饮料换购

题解：

思路1：模拟运算

复杂度：O(log3^N^)

//   n       x         count   cnt
// 啤酒数  喝完瓶盖数  换购  余下瓶盖
// 100     100         33     1
// 33      34          11     1
// 11      12          4      0
// 4       4           1      1
// 1       1           0      1

import java.util.*;
import java.io.*;

class Main {
    
    private static int n;
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        int x = 0, count = 0, cnt = 0;
        int res = n;//初始为啤酒瓶盖数
        while (n != 0) {
            x = n + cnt;
            count = x / 3;
            cnt = x % 3;
            res += count;
            n = count;
        }
        System.out.printf("%d", res);
    }
}

image-20221003184742859

思路2：数学

复杂度：时间复杂度O(1)

学习博客：【微扰理论】小学奥数题 ｜ 不用借酒瓶的那种

import java.util.*;
import java.io.*;

class Main {
    
    private static int n;
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        //公式：瓶数n，每e个瓶盖换一瓶饮料
        //n + (n - 1) / (e - 1)
        System.out.printf("%d", n + (n - 1) / (3 - 1));
    }
}

image-20221003184530564

二、动态规划(dp)

知识点

思路：

  • 化零为整：最值、个数。零散的->集合。
  • 化整为零：集合化为各个子集。

常见模型：组合模型(背包问题)、路线模型(摘花生问题)、序列模型（最长子序列问题）

下面3题是最为常见的三种模型，是对应三道例题y总给出的思路：

下面例题1：

image-20221004204936622

例题2：

image-20221004210519708

例题3：

image-20221004210853224

模板题

例题1：AcWing 2.01背包问题【模板题】

题目链接：2. 01背包问题

学习博客：AcWing 2. 01背包问题（状态转移方程讲解）

解法一：使用二维数组

分析：

定义：dp[i][j]，表示当前是截止到第i个背包，j表示第i个背包体积为j的最大价值数量。

递推方程：dp[i][j] = Math.max(dp[i - 1][j]， dp[i - 1][j - v[i]] + w[i])

dp初始化：默认从i=1，j=1开始。

对应题目给出的输入与输出：

输入：
4 5
1 2
2 4
3 4
4 5

输出：
8

image-20221004171516491

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n^2^) ，本题最大为1000，那么1000x1000=100万，是可以接受的。

解法：

import java.util.*;
import java.io.*;

class Main {
    
    private static final int N = 1005;
    private static int n, V;
    private static int[] v = new int[N], w = new int[N];
    private static int[][] dp = new int[N][N];
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.valueOf(s[0]);
        V = Integer.valueOf(s[1]);
        for (int i = 1; i <= n; i++) {
            s = cin.readLine().split(" ");
            v[i] = Integer.valueOf(s[0]);
            w[i] = Integer.valueOf(s[1]); 
        }
        
        //两层for循环来去枚举出所有dp[i][j]对应背包体积的最大价值
        for (int i = 1; i <= n; i++) {
            //j表示当前经过到第i个背包时，最大的包裹体积
            for (int j = 1; j <= V; j++) {
                if (j >= v[i]) {
                    //尝试去通过递推方程来求最优解
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.printf("%d", dp[n][V]);
    }
}

image-20221004171623413

解法二：使用一维数组

分析：

在解法一种的二维数组我们可以得到一个规律就是我们在每次枚举一组数据时，都是基于上一次记录，也就是说在dp[i]层仅仅只与dp[i-1]层会相关，其他类似于i - 2、i - 3层都不会涉及。

此时递推方程为：dp[i] = Math.max(dp[i], dp[j - v] + w) (j >= v)，计算的过程性质与解法一实质上并没有区别。

image-20221004173214904

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n) ，优化了空间效率

解题：

import java.util.*;
import java.io.*;

class Main {
    
    private static final int N = 1005;
    private static int n, V;
    //一维dp数组
    private static int v, w;
    private static int[] dp = new int[N];
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.valueOf(s[0]);
        V = Integer.valueOf(s[1]);
        
        //两层for循环，记录仅仅使用一维数组
        for (int i = 1; i <= n; i++) {
            s = cin.readLine().split(" ");
            v = Integer.valueOf(s[0]);
            w = Integer.valueOf(s[1]);
            for (int j = V; j >= v; j--) {
                //递推方程
                dp[j] = Math.max(dp[j], dp[j - v] + w);
            }
        }
        System.out.printf("%d", dp[V]);
    }
}

image-20221004173406971

例题2：AcWing 1015. 摘花生【简单】

来源题目：《信息学奥赛一本通》

题目链接：1015. 摘花生

思路1：dp二维数组

分析：

定义dp：dp[i][j]表示在第i行第j列上可取得的最多花生。

确定dp公式：dp[i][j] = Math.max(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j])

题解：

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n^2^)。最大N = 105，不会超时与超出内存空间。

//count

//n m
//arr

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 105;
    static int count, n, m;
    static int[][] arr = new int[N][N];
    //定义dp方程
    static int[][] dp = new int[N][N];
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        count = Integer.valueOf(cin.readLine());
        while (count != 0) {
            String[] s = cin.readLine().split(" ");
            n = Integer.valueOf(s[0]);
            m = Integer.valueOf(s[1]);
            
            //初始化
            for (int i = 1; i <= n; i++) {
                s = cin.readLine().split(" ");
                for (int j = 1; j <= m; j++) {
                    arr[i][j] = Integer.valueOf(s[j - 1]);
                }
            }
            
            //dp：dp[i][j] = Math.max(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[i][j] = Math.max(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]);
                }
            }
            System.out.printf("%d\n", dp[n][m]);
            count--;
        }
    }
}

image-20221004180024003

思路2：dp一维数组

分析：

由于上面dp二维数组每一行仅仅只与上一行有关，所以我们这里可以将其优化为一维数组，推举过程如下：

dp公式为：dp[j] = Math.max(dp[j - 1] + arr[i][j], dp[j] + arr[i][j])

image-20221004182713629

题解：

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n)。最大N = 105，不会超时与超出内存空间。

//count
//n m
//arr

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 105;
    static int count, n, m;
    static int[][] arr = new int[N][N];
    //定义dp方程
    static int[] dp;
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        count = Integer.valueOf(cin.readLine());
        while (count != 0) {
            String[] s = cin.readLine().split(" ");
            n = Integer.valueOf(s[0]);
            m = Integer.valueOf(s[1]);
            
            //初始化
            for (int i = 1; i <= n; i++) {
                s = cin.readLine().split(" ");
                for (int j = 1; j <= m; j++) {
                    arr[i][j] = Integer.valueOf(s[j - 1]);
                }
            }
            
            //重新开辟数组（防止上一组的错误数据）
            dp = new int[N];
            
            //dp：dp[j] = Math.max(dp[j - 1] + arr[i][j], dp[j] + arr[i][j]);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[j] = Math.max(dp[j - 1] + arr[i][j], dp[j] + arr[i][j]);
                }
            }
            System.out.printf("%d\n", dp[m]);
            count--;
        }
    }
}

image-20221004181327972

例题3：AcWing. 4557. 最长上升子序列【简单】

来源：POJ2533 , kuangbin专题

题目链接：4557. 最长上升子序列

学习博客：最长上升子序列（c++图文详解）

分析：

定义：dp[i]，在1-i中有最大长度数量。

转移方程：dp[i] = dp[j] + 1

image-20221004201051595

题解：

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n)。本题最大为1005，时间上不会超过范围。

//定义：dp[i]表示当前在i位置的最长子序列的长度
//状态转移方程：dp[i] = dp[j] + 1 (arr[i] > arr[j] && dp[j] >= dp[i])  最长：res = Math.max(dp[i], res)

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 1005;
    static int n;
    static int arr[] = new int[N];
    //定义dp数组
    static int dp[] = new int[N];
    static int res = 1;
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        String[] s = cin.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(s[i]);
        }
        //初始化dp数组每位都是1（因为自己本身就是1个）
        Arrays.fill(dp, 1);
        //进行递推
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                //若是后面的元素比之前的大，那么直接拿取之前计算的dp长度值+1 && 之前的元素连续数量>=当前元素的数量（无该条件，就可能会被原本小于本身的覆盖掉）
                if (arr[i] > arr[j] && dp[j] >= dp[i]) {
                    //转移方程
                    dp[i] = dp[j] + 1;
                    //求取最大值
                    res = Math.max(res, dp[i]);
                }
            }
        }
        System.out.printf("%d", res);
    }
}

image-20221004201244777

习题

习题1：Acwing 1212. 地宫取宝【中等，蓝桥杯】

分析：

题目类型：摘花生与最长上升子序列的结合版，摘花生扩展版。

三个细节：

  1. 从左到右。
  2. 每次取宝贝是递增。
  3. 到终点取出k件方案数。

根据给出的题分析相应的时间复杂度：f(i, j, k, c)，50x50x12x13x(25)：四层循环+一个循环。

上y总的分析图：

image-20221004214734011

dp定义f[i,j,k,c]：表示从起点走到(i,j)位置，已经取了k间物品，最后一件物品的价值是C的合法方案。

  • k指的是题目要求的k件。
  • c指的是题目要求的物品价值。

状态方程：

  • 不取的情况：dp[i][j][k][c] = dp[i - 1][j][k][c] + dp[i][j - 1][k][c]
  • 取的情况：dp[i][j][k][c] = dp[i - 1][j][k][c] + dp[i][j - 1][k][c] （u > 0 && c == w[i][j]，c’ ∈ (1, v)）

初始化：

f(1, 1, 1, w(1, 1)) = 1 表示取

f(1, 1, 0, -1)=1 表示不取

  • 第四个位置为-1表示的是没有取。由于在数组中无法使用-1表示，所以全部会进行+1，也就是原本是-1 - 12，现在是0 - 13，0表示的就是没有取。【注意：因为这个原因，所以我们需要在给初始的w[i][j]+1】

题解：

复杂度分析：时间复杂度O(n.m.k.c)；空间复杂度O(n.m.k.c)，不超时，满足题目

// 2 2 2
// 1 2
// 2 1

//n = 2 m = 2 k = 2
//arr[n][m]
import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 52, MOD = 1000000007;//int型是23亿，一个MOD就是10亿，最多只能连续两个相加
    static int n, m, k;
    static int[][] w = new int[N][N];
    //定义dp数组
    static int[][][][] dp = new int[N][N][13][14];//dp(i, j, k, c)
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.valueOf(s[0]);
        m = Integer.valueOf(s[1]);
        k = Integer.valueOf(s[2]);
        for (int i = 1; i <= n; i++) {
            s = cin.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                //0表示当前没有取且取得的价值为-1（数组中无法使用-1来表示下标）
                w[i][j] = Integer.valueOf(s[j - 1]) + 1;
            }
        }
        
        //初始化：左上角第一个格子取 or 不取
        dp[1][1][1][w[1][1]] = 1; //在第一个格子上
        dp[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++) { //u表示k，表示在(i,j)取了u件物品
                    for (int v = 0; v <= 13; v++) { //v表示c，表示在(i,j)取了u件物品的价值
                        //不取（直接加上上、左的方案）
                        int val = dp[i][j][u][v];
                        val = (val + dp[i - 1][j][u][v]) % MOD;
                        val = (val + dp[i][j - 1][u][v]) % MOD;
                        dp[i][j][u][v] = val;
                        //取
                        //对于取了0件，但是最后价值是非0的我们要省略掉
                        if(u > 0 && v == w[i][j]) {
                            //这个就是最长子序列模型
                            for (int c = 0; c < v; c++) {
                                val = (val + dp[i - 1][j][u - 1][c]) % MOD;
                                val = (val + dp[i][j - 1][u - 1][c]) % MOD;
                                dp[i][j][u][v] = val;
                            }
                        }
                    }
                }
            }
        }
        
        //统计所有的方案数
        int res = 0;
        for (int i = 0; i <= 13; i++) res = (res + dp[n][m][k][i]) % MOD;
        System.out.printf("%d", res);
    }
}

image-20221005165416696

习题2：AcWing 1214.波动数列【中等，蓝桥杯】

题目链接：1214. 波动数列

题目类型：

  • 背包问题的变形，组合模型
  • 背包问题的简单变种或者组合问题的变种

首先根据题目确定求解的问题：长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？

实际上是一个组合问题，拆分一下就是说求得最后长度为n，和为s的方案(后一项比前一项增加a的方案 + 后一项比前一项增加b的方案)种数。

题目给出了数据范围：1≤n≤1000，那么大概就是n^2^的时间复杂度，那么基本就是两层循环。

给出y总的分析图：

image-20221006122339811

转移方程的推演：f[i][j] = f[i - 1][(j - ai) % n] + f[i - 1][(j + bi) % n]，过程如下：

设定数列的初始值为x，后一个数比前一个数增加或减少称之为d ∈ (+a, -b)，此时就可以列出公式：

s = x + (x + d1) + (x + d1 + d2) + (x + d1 + d2 + d3) + … + (x + d1 + … + d~n-1~)，拆分下为：

x.n + (n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.d~n-1~ = s，将x.n右边的移动到s的式子上即为：

x.n = s - {(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.d~n-1~ }，此时可以化成一个除法公式为：

x = $$ {s - [(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.d~n-1~] \over n} $$，

此时我们来举一个例子，1 = $$ 6 - 2 \over 4 $$，实际上对于后面的2可以使用6 % 4来表示，那么对于上方x的等式，我们可以也依据次来进行表示

s % n = [(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.d~n-1~]

此时若是有i个数，那么后一个数相对于前一个数相加相减的序列为：d1, d2, d3, … di (设+a)

image-20221006115055232

若是想要计算截至当前第i个元素其和，式子为前i - 1个累加的和+当前第i个和 = s % n，也就是上面的s % n = [(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.d~n-1~]

我们用c变量来表示前i - 1个累加的和，最后一项则是上面图片里的a.i 或者-b.i即可，那么就是c + ai = s % n 或者 c - bi = s % n

如何拿到前i - 1累加的和呢？实际上前i - 1个累加的和就是c，那么只需要借助上面的公式c = (s - ai) % n 或者 c = (s + bi) % n即可得到了，那么递推公式为：f[i][s] = f[i - 1][(s - ai) % n] + f[i - 1][(s + bi) % n]

  • 在实际代码中是用j去表示s，那么公式就是：f[i][j] = f[i - 1][(j - ai) % n] + f[i - 1][(j + bi) % n]

初始化：f[0][0] = 1，1个数都不取的话，余数只能为0，所以设置初始位置为1。

题解

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n^2^)

import java.util.*;
import java.io.*;
class Main {
    
    static final int N = 1010, MOD = 100000007;
    static int n, s, a, b;
    static int[][] dp = new int[N][N];
    
    //防止a % b出现负数的情况，a % b 最小值为-b + 1，此时加上b就是>0，最后放置超过b所以再%一次
    public static int getMod(int a, int b) {
        return (a % b + b) % b;
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        s = cin.nextInt();
        a = cin.nextInt();
        b = cin.nextInt();
        //初始化
        dp[0][0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //转移方程
                dp[i][j] = (dp[i - 1][getMod(j - a * i, n)] + dp[i - 1][getMod(j + b * i, n)]) % MOD;
            }
        }
        //防止s % n出现负数，此时就需要调用getMod函数
        System.out.printf("%d", dp[n - 1][getMod(s, n)]);
    }
}

image-20221006122421023

【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
5G游戏 Java 数据结构
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论（0）

抱歉，系统识别当前为高风险访问，暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称，即可参与社区互动！

    *长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

    确认 取消

    目录

    加入云驻计划，成为创作者

    • 华为云周边好礼
    • 免费体验产品
    • 特殊身份标识
    • 线下官方门票
    • 内部专家零距离
    • 与10000+优质创作者共同成长
    立即加入