ACM模版

描述

题解

这个题貌似 dp+线段树 维护也能做，但是纯 dp 解需要的优化就巧妙得很了……看了官方题解和 std 后的感觉就是——还有这种操作.jpg

很有趣的优化手段，我肯定想不起来……对了，大致说一下题意：给定两个序列，求有多少种子序列满足两个对应位置值相等，并且构成波浪序列……题意不难理解，既然是求多少种子序列，很明显就是 dp ，可是在转移时会涉及到前边的很多状态的转移，如果这部分暴力转移的话，复杂度将会很高，显然是不行的，所以这里如果用线段树维护应该是可以的，当然，这个咱们就不说了，就说说官方题解所用的优化，其实这里类似于求前缀和的思维，转移时直接将前缀转移就好了，当然，也不是那么简单的前缀和，之间的转移关系比较复杂，只有满足了这关系的才能搞在一起，维护两个三维数组，……，这里我就不详细说了，看看官方题解就能明白，说得十分详细了。

官方题解：

代码

#include <cstdio>

const int MAXN = 2010;
const int MOD = 998244353;

int n, m;
int a[MAXN], b[MAXN];
int g[MAXN][MAXN][2];
int h[MAXN][MAXN][2];

inline void get_mod(int &x, int y)
{
    x += y;
    if (x >= MOD)
    {
        x -= MOD;
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= m; i++)
        {
            scanf("%d", &b[i]);
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                g[i][j][0] = h[i][j][0] = 0;
                g[i][j][1] = h[i][j][1] = 0;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                for (int k = 0; k < 2; k++)
                {
                    if (a[i] == b[j])
                    {
                        int t = h[i][j][k ^ 1];
                        if (!k)
                        {
                            get_mod(t, 1);
                        }
                        if (t)
                        {
                            get_mod(ans, t);
                            get_mod(g[i + 1][j][k], t);
                        }
                    }
                    if (g[i][j][k])
                    {
                        get_mod(g[i + 1][j][k], g[i][j][k]);
                        if (!k)
                        {
                            if (a[i] > b[j])
                            {
                                get_mod(h[i][j + 1][k], g[i][j][k]);
                            }
                        }
                        else if (a[i] < b[j])
                        {
                            get_mod(h[i][j + 1][k], g[i][j][k]);
                        }
                    }
                    if (h[i][j][k])
                    {
                        get_mod(h[i][j + 1][k], h[i][j][k]);
                    }
                }
            }
        }

        printf("%d\n",ans);
    }

    return 0;
}