蓝桥模拟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];
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信