蓝桥模拟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。

题目大意

就是一串数列，要求偶数项要小于前面那项的值，奇数项要大于前面那项的值，长度为m，数字为1~n。求这串数列的最多组成方案。

解题思路

因为奇数项和偶数项的要求不同，所以需要分开来考虑。

奇数项的方案数等于前面一项的所有小于该项值的方案数之和。

偶数项的方案数等于前面一项的所有大于该项值的方案数之和。

于是可以得出定义:
dp[i] [j] (i为奇数)等于第i项大于等于j的方案数。

dp[i] [j] (i为偶数)等于第i项小于等于j的方案数。

所以状态转移方程为:

1、dp[i] [j] = dp[i - 1] [j + 1] + dp[i] [j - 1];

2、dp[i] [j] = dp[i - 1] [j - 1] + dp[i] [j + 1];

初始化为dp[1] [j] =n - j +1;

如果m为奇数的话，答案为dp[i] [1];

m为偶数的话，答案为dp[i] [n];

(哎。。DP是真的难。。主要是特别难想

基本DP题都能杀我，还是不会DP。

需要多去学习啊。。

别问，问就是题量不够。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
using namespace std;

int dp[1010][1010];

int main() {
	int n, m;
	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 % 2 == 0) {//这里推荐用i&1来判断，比取余要更快
			for (int j = 1; j <= n; j++) {
				dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % 10000;
			}
		}
		else {
			for (int j = n; j >= 1; j--) {
				dp[i][j] = (dp[i - 1][j - 1] + dp[i][j + 1]) % 10000;
			}
		}
	}
	if (m % 2 == 0) {
		cout << dp[m][n];
	}
	else cout << dp[m][1];
}