Wavel Sequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 502 Accepted Submission(s): 267
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).
Source
2017 Multi-University Training Contest - Team 4
题意：规定a1< a2 > a3 < a4 > a5 < a6……的数组为波浪数组，且第一个数必须为波谷，给定数组a，b，找出a中的波浪数组在b中有几组存在
解题思路：dp[i][0]存放b[i]作为波谷时的情况，dp[i][1]存放b[i]作为波峰时的情况。然后枚举a数组，在b数组中去找和a[i]一样的位置，找到后更新答案
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
const LL mod = 998244353;
int a[2010], b[2010];
LL dp[2010][2];
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]);
LL ans = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
LL cnt0 = 1, cnt1 = 0;
for (int j = 1; j <= m; j++)
{
if (a[i] == b[j])
{
dp[j][0] += cnt0, dp[j][1] += cnt1;
(ans += cnt0 + cnt1) %= mod;
}
else if (a[i] > b[j]) (cnt1 += dp[j][0]) %= mod;
else (cnt0 += dp[j][1]) %= mod;
}
}
printf("%lld\n", ans);
}
return 0;
}
