AcWing 藍橋杯AB組輔導課 03、數學與簡單dp

文章目錄

前言
一、數學

例題

例題1：AcWing 1205.買不到的數目【簡單，藍橋杯】
例題2：螞蟻感冒【簡單，藍橋杯】
例題3：飲料換購【簡單，藍橋杯】

二、動态規劃(dp)

知識點
模闆題

例題1：AcWing 2.01背包問題【模闆題】

解法一：使用二維數組
解法二：使用一維數組

例題2：AcWing 1015. 摘花生【簡單】
例題3：AcWing. 4557. 最長上升子序列【簡單】

習題

習題1：Acwing 1212. 地宮取寶【中等，藍橋杯】
習題2：AcWing 1214.波動數列【中等，藍橋杯】

前言

前段時間為了在面試中能夠應對一些算法題走上了刷題之路，大多數都是在力扣平台刷，目前是300+，再加上到了新學校之後，了解到學校也有組織藍橋杯相關的程式競賽，打算再次嘗試一下，就想系統學習一下算法（再此之前是主後端工程為主，算法了解不多刷過一小段時間），前段時間也是第一次通路acwing這個平台，感覺上面課程也是比較系統，平台上題量也很多，就打算跟着acwing的課程來走一段路，大家一起共勉加油！

目前是打算參加Java組，是以所有的題解都是Java。

本章節數學及簡單dp的習題一覽：包含所有題目的Java題解連結

例題的前三題是藍橋杯關于數學内容；後三題是簡單dp内容。
習題則是藍橋杯題，相對于例題是進行了一個擴充。

例題：

AcWing 1205. 數學買不到的數目 Java題解
AcWing 1211. 螞蟻感冒 Java題解
AcWing 1216. 數學-藍橋杯題飲料換購 Java題解(模拟、數學)
AcWing 2. 動态規劃-模闆題 01背包問題 Java題解（二維數組、一維數組解法+圖示）
AcWing 1015. 動态規劃習題摘花生 Java題解（二維數組、一維數組）
AcWing 4557. 動态規劃-最長上升子序列 Java題解

習題：

AcWing 1212. 動态規劃(路線+序列模型組合題) 地宮取寶 Java題解
AcWing 1214. 動态規劃-藍橋杯波動數列 Java題解(詳細推演)

其中背包問題（算法基礎課）、摘花生(提高課)、最長子序列(提高課)

一、數學

藍橋杯中的數學更像腦筋急轉彎，涉及到一些數學的模型。

競賽中的考察比較深的數學知識。

例題

例題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);
    }
}

思路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);
    }
}

思路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--;
        }
    }
}

例題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);
        }
    } 
}

例題3：飲料換購【簡單，藍橋杯】

題目連結：1216. 飲料換購

題解：

思路1：模拟運算

複雜度：O(log3N)

//   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);
    }
}

思路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));
    }
}

二、動态規劃(dp)

知識點

思路：

化零為整：最值、個數。零散的->集合。
化整為零：集合化為各個子集。

常見模型：組合模型(背包問題)、路線模型(摘花生問題)、序列模型（最長子序列問題）

下面3題是最為常見的三種模型，是對應三道例題y總給出的思路：

下面例題1：

例題2：

例題3：

模闆題

例題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開始。

對應題目給出的輸入與輸出：

複雜度分析：時間複雜度O(n2)；空間複雜度O(n2) ，本題最大為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]);
    }
}

解法二：使用一維數組

分析：

在解法一種的二維數組我們可以得到一個規律就是我們在每次枚舉一組資料時，都是基于上一次記錄，也就是說在dp[i]層僅僅隻與dp[i-1]層會相關，其他類似于i - 2、i - 3層都不會涉及。

此時遞推方程為：

dp[i] = Math.max(dp[i], dp[j - v] + w)

(j >= v)，計算的過程性質與解法一實質上并沒有差別。

複雜度分析：時間複雜度O(n2)；空間複雜度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]);
    }
}

例題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(n2)；空間複雜度O(n2)。最大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--;
        }
    }
}

思路2：dp一維數組

分析：

由于上面dp二維數組每一行僅僅隻與上一行有關，是以我們這裡可以将其優化為一維數組，推舉過程如下：

dp公式為：

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

題解：

複雜度分析：時間複雜度O(n2)；空間複雜度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--;
        }
    }
}

例題3：AcWing. 4557. 最長上升子序列【簡單】

題目連結：4557. 最長上升子序列

學習部落格：最長上升子序列（c++圖文詳解）

分析：

定義：dp[i]，在1-i中有最大長度數量。

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

題解：

複雜度分析：時間複雜度O(n2)；空間複雜度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);
    }
}

習題

習題1：Acwing 1212. 地宮取寶【中等，藍橋杯】

分析：

題目類型：摘花生與最長上升子序列的結合版，摘花生擴充版。

三個細節：

從左到右。
每次取寶貝是遞增。
到終點取出k件方案數。

根據給出的題分析相應的時間複雜度：f(i, j, k, c)，50x50x12x13x(25)：四層循環+一個循環。

上y總的分析圖：

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);
    }
}

習題2：AcWing 1214.波動數列【中等，藍橋杯】

題目連結：1214. 波動數列

題目類型：

背包問題的變形，組合模型
背包問題的簡單變種或者組合問題的變種

首先根據題目确定求解的問題：長度為 n 和為 s 而且後一項總是比前一項增加 a 或者減少 b 的整數數列可能有多少種呢？

實際上是一個組合問題，拆分一下就是說求得最後長度為n，和為s的方案(後一項比前一項增加a的方案 + 後一項比前一項增加b的方案)種數。

題目給出了資料範圍：1≤n≤1000，那麼大概就是n2的時間複雜度，那麼基本就是兩層循環。

給出y總的分析圖：

轉移方程的推演：

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 + … + dn-1)，拆分下為：

x.n + (n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.dn-1 = s，将x.n右邊的移動到s的式子上即為：

x.n = s - {(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.dn-1 }，此時可以化成一個除法公式為：

x = ，

此時我們來舉一個例子，1 = ，實際上對于後面的2可以使用6 % 4來表示，那麼對于上方x的等式，我們可以也依據次來進行表示

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

此時若是有i個數，那麼後一個數相對于前一個數相加相減的序列為：d1, d2, d3, … di (設+a)

若是想要計算截至目前第i個元素其和，式子為前i - 1個累加的和+目前第i個和 = s % n，也就是上面的s % n = [(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.dn-1]

我們用

變量來表示前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(n2)；空間複雜度O(n2)

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)]);
    }
}

AcWing 藍橋杯AB組輔導課 03、數學與簡單dp

文章目錄

前言

一、數學

例題

例題1：AcWing 1205.買不到的數目【簡單，藍橋杯】

例題2：螞蟻感冒【簡單，藍橋杯】

例題3：飲料換購【簡單，藍橋杯】

二、動态規劃(dp)

知識點

模闆題

例題1：AcWing 2.01背包問題【模闆題】

解法一：使用二維數組

解法二：使用一維數組

例題2：AcWing 1015. 摘花生【簡單】

例題3：AcWing. 4557. 最長上升子序列【簡單】

習題

習題1：Acwing 1212. 地宮取寶【中等，藍橋杯】

習題2：AcWing 1214.波動數列【中等，藍橋杯】

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希