HDU 6078 Wavel Sequence （dp）

HDU 6078 Wavel Sequence （dp）

Description

Input

The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.In each test case, there are 2 integers n,m(1≤n,m≤2000) in the first line, denoting the length of a and b.In the next line, there are n integers a1,a2,…,an(1≤ai≤2000), denoting the sequence a.Then in the next line, there are m integers b1,b2,…,bm(1≤bi≤2000), denoting the sequence b.

Output

For each test case, print a single line containing an integer, denoting the answer. Since the answer may be very large, please print the answer modulo 998244353.

Sample Input

13 51 5 34 1 1 5 3

Sample Output

10

题意

定义波浪序列为满足 a1< a2 > a3 < a4 … 的序列，现给出两个数组 a 和 b ，从 a 中选出满足波浪序列的一个子序列 f ， b 中选出满足波浪序列的子序列 g ，求有多少种选法满足 f = g 。

思路

​​dp[0][j]​​​ 代表以 ​​b[j]​​ 结尾且最后为波谷的情况数目。

​​dp[1][j]​​​ 代表以 ​​b[j]​​ 结尾且最后为波峰的情况数目。

显然，结尾为波谷的情况可以由 波峰 + 一个小的数 转移而来，而结尾为波峰的情况可以由 波谷 + 一个大的数 转移而来。

因此我们定义 ​​ans0、ans1​​​ 分别表示在该轮中相对于 ​​a[i]​​​ 来说 ​​b[j]​​ 可作为波谷与波峰的数目。

枚举每一个 ​​a[i]​​​ ，并且判断其与 ​​b[j]​​ 的大小关系：

若​​a[i] < b[j]​​​ ，则说明​​b[j]​​ 可作为一个波峰出现若​​a[i] > b[j]​​​ ，则说明​​b[j]​​ 可作为一个波谷出现若​​a[i] = b[j]​​​ ，则说明找到一个对​​f = g​​ 有贡献的值，更新答案

AC 代码

#includeusing namespace std;typedef __int64 LL;const int mod = 998244353;const int maxn = 2100;int a[maxn],b[maxn];LL dp[2][maxn];int main(){ int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。