摆动序列
原题目链接
题目描述
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。
即对于任意整数 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]
