蓝桥杯模拟赛 摆动序列 题目+题解

摆动序列

  大家好，我叫亓官劼（qí guān jié ）

题目

问题描述

如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 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。

题解

写在这题前面，有很多小伙伴反应这题的题解代码看不懂代码，这样吧，博主现在在外面，今晚回去我写一下这题动态规划解法的详细题解和几种动态规划解法的逐渐优化的过程，如果有需要的小伙伴可以今晚或者明天(​​2020.4.20​​​)来查看相应的题解。
——2020.04.19

本题题解的详细解释博文已发布，如果需要可以查看，地址为：​​蓝桥杯模拟赛 摆动序列 详细题解 多种解法​​

​ 这题如果直接暴力求解的话，估计只能够过50%的数据，所以还是得使用dp来进行求解。​​dp[i][j]​​​表示第i位数时，最大数为m时共有多少个。然后根据题目要求：如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。所以我们每次处理都需要判断i的奇偶，这里使用​​i&1​​​进行判断，这里使用他的原因在之前的另一篇博客中写了，有不懂的小伙伴可以去参考一下，地址为：​​为什么同样的算法，你的程序却一直超时？ 算法竞赛你不得不知道的小技巧​​​。然后我们为边界赋值，这里赋值只有1位数的时，最大数的不同时，可能的种类，这里初始化为​​dp[1][i] = n - i + 1;​​。然后我们从

​ 下面我们来详细的解释一下dp的过程。这里我们计算的时候先从第一行开始，为第一行进行一个初始化，初始化为下一行可以选择的值的数目，即当前所能组成的摆动数列的个数。我们初始化​​dp[1][i] = n - i + 1;​​

第一行中，令 ​​d[1][j]​​为：第1个数选择大于等于 j的数的方案总数。

从第二行开始：

​ 奇数行中，令 ​​d[i][j]​​​为：第i个数选择大于等于j的数时的方案总数。
​ 偶数行中，令 ​​d[i][j]​​为：第i个数选择小于等于j的数时的方案总数。

即从第二行开始，如果行数为偶数行，那么我们当前可能的数目为：​​dp[i][j] = (dp[i-1][j+1] + dp[i][j-1]) % 10000;​​​,如果为奇数行则：​​dp[i][j] = (dp[i-1][j-1] + dp[i][j+1]) % 10000;​​。

​ 然后这样的话，如果我们总的长度为奇数的话，那么就是​​dp[m][1]​​​,如果是偶数，则为​​dp[m][n]​​。

#include 
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;
}