17暑假多校联赛4.12 HDU 6078 Wavel Sequence

Wavel Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)  

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).

  题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=6078  

分析

题意：规定a1< a2 > a3 < a4 > a5 < a6……的数组为波浪数组，且第一个数必须为波谷，给定数组a，b，找出a中的波浪数组在b中有几组存在 将a中的值挨个与b中的各个值比较，相等的话可以做波谷也可以作为波峰，如果a比b大可以作为波谷继承前面波峰的数量，反之，作为波峰继承前面的波谷数量，不断继承之后得到的是可以成为波浪数组又在a和b中都存在的数量  

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=998244353; const int maxn=2010; int a[maxn],b[maxn]; ll dp[maxn][2]; ///dp[i][0]存放b[i]作为波谷时的情况，dp[i][1]存放b[i]作为波峰时的情况 int main() { int t; scanf("%d",&t); while(t--) { int n,m; 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]); long long ans=0; memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++) { ll cnt0=1,cnt1=0;///cnt0表示波谷位置，cnt1表示波峰位置 for(int j=1; j<=m; j++) { if(a[i]==b[j])///如果相等，可单独作为波谷成为一组情况 { dp[j][0]+=cnt0,dp[j][1]+=cnt1; ans=(ans+cnt0+cnt1)%mod;///加上其作为波峰波谷的总情况数 } else if(a[i]>b[j])(cnt1+=dp[j][0])%=mod; ///a[i]>b[j]，那么b[j]可以作为波谷，继承前面的波谷 else (cnt0+=dp[j][1])%=mod; ///反之，那么b[j]可以作为波峰，继承前面的波峰 } } printf("%lld\n",ans); } return 0; }