藍橋杯模擬賽 擺動序列 詳細題解 多種解法

  大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~部落格地址為：亓官劼的部落格，亓官劼的部落格2。

本文原創為亓官劼，請大家支援原創，部分平臺一直在盜取博主的文章！！！

博主目前僅在CSDN中寫部落格，唯一部落格更新的地址為：亓官劼的部落格，亓官劼的部落格2。

---

第十一屆 藍橋杯 省 模擬賽 完整題目+題解地址為：第十一屆 藍橋杯 省 模擬賽 試題+題解

---

有很多小夥伴反應說在題解中寫的這題的動態規劃的程式碼看不懂，不知道為什麼要這樣寫，所以本文來詳細的解釋一下這題的解法，以及動態規劃如何進行優化的過程。

題目

問題描述

如果一個序列的奇數項都比前一項大，偶數項都比前一項小，則稱為一個擺動序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。
　　小明想知道，長度為 m，每個數都是 1 到 n 之間的正整數的擺動序列一共有多少個。

輸入格式

輸入一行包含兩個整數 m，n。

輸出格式

輸出一個整數，表示答案。答案可能很大，請輸出答案除以10000的餘數。

樣例輸入

3 4

樣例輸出

14

樣例說明

以下是符合要求的擺動序列：
　　2 1 2
　　2 1 3
　　2 1 4
　　3 1 2
　　3 1 3
　　3 1 4
　　3 2 3
　　3 2 4
　　4 1 2
　　4 1 3
　　4 1 4
　　4 2 3
　　4 2 4
　　4 3 4

評測用例規模與約定

對於 20% 的評測用例，1 <= n, m <= 5；
　　對於 50% 的評測用例，1 <= n, m <= 10；
　　對於 80% 的評測用例，1 <= n, m <= 100；
　　對於所有評測用例，1 <= n, m <= 1000。

題解一：暴力+dfs

  這題也可以使用暴力+dfs的方法進行一個暴力的搜尋符合要求的序列，但是在本題的數量級中，此種解法必然超時，所以在此就不貼程式碼了，無意義。

題解二：動態規劃（一）基本動態規劃

  這題既然暴力是無法過所有樣例的話，那我們就需要尋求其他的解法了。這裡先寫一個動態規劃的解法，我們來分析我們的目前的問題。問題為：如果一個序列的奇數項都比前一項大，偶數項都比前一項小，則稱為一個擺動序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。小明想知道，長度為 m，每個數都是 1 到 n 之間的正整數的擺動序列一共有多少個。

  我們使用dp[i][j]來表示在第i位數選擇j時，可以選擇的數量。那麼對於任意的dp[i][j]，我們可以根據題意分為兩種情況，即i為奇數和i為偶數。

  當i為奇數時，根據題意，奇數項是要比前一項大，則我們的第i位數的選擇數為j時，我們可以組成的序列的數量為：第i-1位時選擇，數為1到j-1的和，即dp[i][j] = dp[i-1][1] + dp[i-1][2] + ...... + dp[i-1][j-1]。
  當i為偶數時，根據題意，偶數項要比前一項小，則我們的第i位數為j時，我們可以組成的序列的數量為：第i-1位時，數為j+1到n的和，即dp[i][j] = dp[i-1][j+1] + dp[i-1][j+2] + ....... + dp[i-1][n]。

  這樣我們動態規劃的狀態轉移方程就出來了：

• 當i為奇數時：dp[i][j] = dp[i-1][1] + dp[i-1][2] + ...... + dp[i-1][j-1]
• 當i為偶數時:dp[i][j] = dp[i-1][j+1] + dp[i-1][j+2] + ....... + dp[i-1][n]

  下面我們來對dp陣列進行初始化，我們發現我們每一項都需要使用到i-1位時的資料，即上一位的資料，同時我們發現當i = 1時，dp[1][j] = 1是顯然成立的。即我們第一位數選擇j時，只有一種序列。

  這樣我們整個的演演算法的分析就完成了，下面我們只需要將我們的想法使用程式來進行實現即可，完整的題解程式碼為：

#include <iostream>
using namespace std;
int dp[1004][1004];
int main() {
    // m為長度，n為數的範圍
    int m,n;
    cin>>m>>n;

    for(int i = 1; i <= n; i++)
        dp[1][i] = 1;
    for(int i = 2; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(i&1){
                int temp = 0;
                for(int k = 1; k <= j-1; k++){
                    temp = (temp + dp[i-1][k]) % 10000;
                }
                dp[i][j] = temp;
            } else{
                int temp = 0;
                for(int k = j+1; k <= n; k++){
                    temp = (temp + dp[i-1][k]) % 10000;
                }
                dp[i][j] = temp;
            }

        }
    }
    int ans = 0;
    for(int i = 0; i <= n; i++){
        ans += dp[m][i];
    }
    cout<<ans;
    return 0;
}

  需要注意的是，由於我們dp[i][j]表示的是第i為選擇數j時的序列的數量，所有我們最終m位數最大值為n時，我們可以組成的序列數量為dp[m][1] + dp[m][2] + ......... + dp[m][n]。

  此種解法的時間複雜度為O(mn^2)，即O(N3)的效率，對於本題的資料規模，我們發現只可以過80%的資料，因為題目要求對於所有評測用例，1 <= n, m <= 1000。所以我們本種動態規劃解法只可以得到80%的分數，如果想要得到滿分，我們還得進行進一步的優化。

題解三：動態規劃（二） 進一步優化演演算法

  我們在題解二中發現，即使我們使用動態規劃演演算法，也只能有O(mn^2)的時間效率，在本題的資料規模中，只可以過前80%的資料，得到80%的分數，如果想要拿全分的話，那我們就只能進一步的優化我們的演演算法了。

  我們分析題解二的演演算法，發現我們每次求解dp[i][j]的時候都進行了一次重複的計算，就是計算第1到j-1項的和或者第j+1到n項的和，這裡的計算我們是可以通過優化將它省略的。這樣我們就可以將我們的時間複雜度從O(n^3)降到O(n2)，直接降低一個數量級。如果我們要省略這裡的重複的求和計算，我們就需要改變我們這裡dp[i][j]儲存的資訊。這裡我們改為使用dp[i][j]表示的資訊，當i為偶數時，dp[i][j]表示第i個數選擇小於等於j時的數列數；當i為奇數時，dp[i][j]表示第i個數選擇大於等於j是的數列數。

  那麼對於任意的dp[i][j]，當i為奇數的時候，奇數項要比前一項大，所以我們當前的dp[i][j]的值為dp[i-1][j-1]+dp[i][j+1]。即dp[i][j] = dp[i-1][j-1] + dp[i][j+1]，由於我們此時的dp[i][j]的值需要使用到dp[i][j+1]，所以我們這裡遍歷倒著遍歷。當i為偶數時，偶數項比前一項小，所以我們dp[i][j]的值為dp[i-1][j+1] + dp[i][j-1]。即dp[i][j] = dp[i-1][j+1] + dp[i][j-1],這裡我們就需要進行正向的遍歷。

在這種解法中，我們發現我們在dp[i][j]更新的遍歷中，代替了累加的計算。在i為奇數的時候，我們的j從n到1進行遍歷，dp[i][j] = dp[i-1][j-1] + dp[i][j+1]；當i為偶數時，我們的j從1到n進行遍歷，dp[i][j] = dp[i-1][j+1] + dp[i][j-1]。在dp[i][j]的計算中直接記錄了累加的值，避免了大量的計算。

這時我們的狀態轉移方程為：

• 當i為奇數時：dp[i][j] = dp[i-1][j-1] + dp[i][j+1]

• 當j為偶數是：dp[i][j] = dp[i-1][j+1] + dp[i][j-1]

  這時我們就需要對dp陣列進行初始化，在這種解法中，我們由於dp[i][j]與解法二中表示的意義是不一樣的，所以我們這的初始化也不同。在這裡我們的dp[1][j] = n - i +1。

  這時我們的m如果為奇數時，所能組成的序列數量為dp[m][1],如果n為偶數，所能組成的序列數量為dp[m][n]

這樣就將我們的演演算法的時間複雜度從O(N^{3)優化到了O(N}2)。完整的題解程式碼為：

#include <iostream>
using namespace std;
int dp[1004][1004];
int main() {
    // m為長度，n為數的範圍
    int m,n;
    cin>>m>>n;

    for(int i = 1; i <= n; i++)
        dp[1][i] = n - i + 1;

    for(int i = 2; i <= m; i++)
        if(i & 1)
            for(int j = n; j >= 1; j--)
                dp[i][j] = (dp[i-1][j-1] + dp[i][j+1]) % 10000;
        else
            for(int j = 1; j <= n; j++)
                dp[i][j] = (dp[i-1][j+1] + dp[i][j-1]) % 10000;

    int ans = m & 1 ? dp[m][1] : dp[m][n];

    cout<<ans;

    return 0;
}

---

  大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~部落格地址為：亓官劼的部落格，亓官劼的部落格2。

本文原創為亓官劼，請大家支援原創，部分平臺一直在盜取博主的文章！！！

博主目前僅在CSDN中寫部落格，唯一部落格更新的地址為：亓官劼的部落格，亓官劼的部落格2。