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