藍橋杯學習記錄||1214. 波動數列

AcWing||1214. 波動數列

活動位址：https://www.acwing.com/activity/content/19/

考察要點：DP

題目要求

觀察這個數列：

1 3 0 2 -1 1 -2 …

這個數列中後一項總是比前一項增加2或者減少3，且每一項都為整數。

棟棟對這種數列很好奇，他想知道長度為 n 和為 s 而且後一項總是比前一項增加 a 或者減少 b 的整數數列可能有多少種呢？

輸入格式

共一行，包含四個整數 n,s,a,b，含義如前面所述。

輸出格式

共一行，包含一個整數，表示滿足條件的方案數。

由于這個數很大，請輸出方案數除以 100000007 的餘數。

資料範圍

1≤n≤1000,

−109≤s≤109,

1≤a,b≤106

輸入樣例：

4 10 2 3

輸出樣例：

2

樣例解釋

兩個滿足條件的數列分别是

2 4 1 3 和 7 4 1 -2。

題目位址：https://www.acwing.com/problem/content/1216/

解析：看起來像數列的問題，但是本質上還是背包問題，每次都有兩個選擇 加a 或 減b ，使用 f[i][j] 表示考慮前 i 個數，前 i 個數的總和 % n 為 j 的方案的集合

注意：c++取餘可能出現負數，使用寫一個函數求正餘數：先讓 a 對 b進行一次取餘，結果的範圍在 （-b，b）之間，+b後再次取餘，就一定是正的了。

如果不了解，也可以在第一次取餘後加一個判斷如果為負數，就直接 加 b

int getMod(int a, int b)  //求 a % b 的正餘數
 {
     int x = a % b;
     if(x < 0) x += b;
     return x;
 } 
           

代碼思路 先枚舉前 i 個數和各種餘數的情況，i 加上 i - 1 的各種結果。最後輸出 餘數 與 s % n相等的集合

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 using namespace std;
 
 int n, s, a, b;
 const int N = 1010, MOD = 100000007;
 int f[N][N];   //隻考慮前i項，且目前的總和%n為j的方案的集合
 
 int getMod(int a, int b)  //求 a % b 的正餘數
 {
     return (a % b + b) % b;
 }
 
int main()
{
    cin >> n >> s >> a >> b;
    
    f[0][0] = 1;  // 【一個數都沒取】【餘數為0】= 一種方案
    
    //枚舉所有狀态
    for(int i = 1; i < n; i ++)
        for (int j = 0; j < n; j ++ )   //餘數範圍【0~n-1】
        f[i][j] = (f[i - 1][getMod(j - a *(n - i), n)] + f[i - 1][getMod(j + b *(n - i), n)]) % MOD;
        
    cout << f[n - 1][getMod(s, n)] << endl;
    
    return 0;
}
           

本題:1214. 波動數列

代碼參考:視訊講解