擺動序列

原題目鏈接

題目描述

如果一個序列的奇數項都比前一項大，偶數項都比前一項小，則稱為一個擺動序列。
即對于任意整數 i（i ≥ 1）滿足：

• a?? < a????，
• a???? > a??

小明想知道，長度為 m，每個數都是 1 到 n 之間的正整數的擺動序列一共有多少個。

---

輸入描述

輸入一行包含兩個整數 m 和 n：

• 1 ≤ m, n ≤ 1000

---

輸出描述

輸出一個整數，表示答案。由于答案可能很大，請輸出答案 模 10000 的結果。

---

輸入示例

3 4

輸出示例

14

c++代碼

#include<bits/stdc++.h>using namespace std;int main() {int m, n;cin >> m >> n;vector<int> last(n + 1), now(n + 1);for (int i = 1; i <= n; i++) last[i] = i;for (int i = 2; i <= m; i++) {for (int j = 1; j <= n; j++) {now[j] = now[j - 1] + ((i % 2 == 0) ? last[n] - last[j] : last[j - 1]);now[j] %= 10000;}last = now;}cout << last[n];return 0;
}//by wqs

思路解析

dp[i][j]表示第i個數選擇小于等于j的數有多少方案
dp[i][j] = dp[i][j - 1] + 選擇j有多少方案
=dp[i][j - 1] + (i % 2 == 0) ? dp[i - 1][n] - dp[i - 1][j] : dp[i - 1][j - 1]