HDU-2017 多校训练赛4-1012-Wavel Sequence

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("%dn",ans);
}
return 0;
}

最后

以上就是呆萌绿草为你收集整理的HDU-2017 多校训练赛4-1012-Wavel Sequence的全部内容，希望文章能够帮你解决HDU-2017 多校训练赛4-1012-Wavel Sequence所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。