Wavel Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 511    Accepted Submission(s): 272 题目链接：点击打开链接 Problem Description Have you ever seen the wave? It's a wonderful view of nature. Little Q is attracted to such wonderful thing, he even likes everything that looks like wave. Formally, he defines a sequence  a1,a2,...,an  as ''wavel'' if and only if  a1<a2>a3<a4>a5<a6... Picture from Wikimedia Commons Now given two sequences  a1,a2,...,an  and  b1,b2,...,bm , Little Q wants to find two sequences  f1,f2,...,fk(1≤fi≤n,fi<fi+1)  and  g1,g2,...,gk(1≤gi≤m,gi<gi+1) , where  afi=bgi  always holds and sequence  af1,af2,...,afk  is ''wavel''. Moreover, Little Q is wondering how many such two sequences  f  and  g  he can find. Please write a program to help him figure out the answer.   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 1 3 5 1 5 3 4 1 1 5 3   Sample Output 10 Hint (1)f=(1),g=(2). (2)f=(1),g=(3). (3)f=(2),g=(4). (4)f=(3),g=(5). (5)f=(1,2),g=(2,4). (6)f=(1,2),g=(3,4). (7)f=(1,3),g=(2,5). (8)f=(1,3),g=(3,5). (9)f=(1,2,3),g=(2,4,5). (10)f=(1,2,3),g=(3,4,5). 题意：

给出一个有n（<=2000）个数字的序列 a(ai <=2000) 再给出一个有m（m<=2000）个

数字的序列 b（bi<=2000） ，定义波浪序列为：x1<x2>x3<x4……（注意第一次必须

是上升，不能是下降，也就是说第一项必须是波谷，这也可以让我们明白，相对于

一个数来说，不管大小，它都可以作为 波谷的，因为下一个数一定要大于它）。现

在要求从a中找到序列 f：f1，f2，……fk。相对应的在b中找序列g：g1，g2，……

gk。（k>=1）使得每个a_fi =b_gi，同时满足a_f1,a_f2,a_f3……a_fk为波浪序列。求

不同的fg映射有多少种选取方式。

a，b中分别从前向后选取k个数字。然后相对应的 a 中选择的每个位置的数字要和 b 

中选择的对应位次的数字相同。（当然如果a数组出现过x，而b没有出现过x，显然x

不可能被选取），而 f 、g 则是相对应的下标。要满足选取出来的这个数字序列是一

个波浪序列。显然波浪序列中的数字分成两种：波峰和波谷。

总体来说，这个题就是a、b数组之间的匹配问题，同时满足是一个波浪序列。

分析： 用一个二维数组dp来存储b数组中每个数字作为波峰和波谷的两种情况：  

       dp[ ][0]用来表示当前数字为波谷时的情况 

       dp[ ][1]用来表示当前数字为波峰时的情况 

       每轮查找都不断更新dp的值 

再用一个二维数组sum来存储b数组中每个数字作为波峰和波谷的次数，它的作用

其实是为在b数组中如果遇 到下一个和a[i]相等的数时做统计。

用sum[][0]来存储该数字在波谷时的总的情况数 

       sum[ ][1]用来存储该数字在波峰时的总的情况数 

其实sum的作用是为后面的查询做统计（这个代码是用b数组作统计的）

       下面我们来看代码实现吧。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 998244353; const int N = 2e3+5; int b[N], a[N]; LL sum[N][2], dp[N][2];///sum存储b数组中每位数字两种情况下的总值； int main() { int T, n, m; scanf("%d", &T); while(T--) { memset(sum,0,sizeof(sum)); memset(dp,0,sizeof(dp)); 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]); LL ans = 0;///ans是计算b中所有数字能当波峰和波谷的所有情况，也就是最终的答案 for(int i = 1; i <= n; i++)///以a数组当前查询的点作为波浪结束点 { LL cnt0 = 1, cnt1 = 0;///cnt0表示波谷位置，cnt1表示波峰位置 for(int j = 1; j <= m; j++) { if(a[i] == b[j])///如果在b数组中查询到有相等的，则说明该点是波浪的结束点， ///开始统计它作为波峰和波谷的情况 { dp[j][0] = cnt0;///dp[][0]表示b[j]在波谷的情况 dp[j][1] = cnt1;///dp[][1]表示b[j]在波峰的情况 ans = (ans+cnt1+cnt0)%MOD;///ans表示计算两种情况的总合 } else if(b[j] < a[i])///如果b[j]<a[i],说明b[j]的值可以做a[i]的值得波谷，换句话说， ///当在b数组中找到与a[i]值相同的数时，可以统计它相对作为波峰的情况 (cnt1 += sum[j][0]) %= MOD; else///同上理解 (cnt0 += sum[j][1]) %= MOD; } for(int j = 1; j <= m; j++) { if(b[j] == a[i]) { (sum[j][0] += dp[j][0]) %= MOD; (sum[j][1] += dp[j][1]) %= MOD; } } } printf("%lld\n", ans); } return 0; }