題目來(lái)戳呀

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…

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

題意：

給出a，b數(shù)列，定義波浪數(shù)列為a1＜a2>a3＜a4>a5 ＜a6…（第一個(gè)數(shù)必須小于第二個(gè)數(shù)）。
現(xiàn)在找出f,g，使得 afi = bgi ，同時(shí) afi 為波浪序列，求滿足此映射關(guān)系的f,g的種數(shù)。

想法：

dp[0][j] 代表以 b[j] 結(jié)尾且最后為波谷的情況數(shù)目。

dp[1][j] 代表以 b[j] 結(jié)尾且最后為波峰的情況數(shù)目。

顯然，結(jié)尾為波谷的情況可以由 波峰 + 一個(gè)小的數(shù) 轉(zhuǎn)移而來(lái)，而結(jié)尾為波峰的情況可以由 波谷 + 一個(gè)大的數(shù) 轉(zhuǎn)移而來(lái)。

因此我們定義 ans0、ans1 分別表示在該輪中相對(duì)于 a[i] 來(lái)說(shuō) b[j] 可作為波谷與波峰的數(shù)目。

枚舉每一個(gè) a[i] ，并且判斷其與 b[j] 的大小關(guān)系：

若 a[i] < b[j] ，則說(shuō)明 b[j] 可作為一個(gè)波峰出現(xiàn)
若 a[i] > b[j] ，則說(shuō)明 b[j] 可作為一個(gè)波谷出現(xiàn)
若 a[i] = b[j] ，則說(shuō)明找到一個(gè)對(duì) f = g 有貢獻(xiàn)的值，更新答案
想法來(lái)自這里 講的真的清楚

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll p=998244353; int a[2005],b[2005]; ll dp[2][2005]; int main() {int t;scanf("%d",&t);while (t--){int n,m;ll sum=0;memset(dp,0,sizeof(dp));scanf("%d %d",&n,&m);for (int i=0; i<n; i++)scanf("%d",&a[i]);for (int i=0; i<m; i++)scanf("%d",&b[i]);for (int i=0; i<n; i++){ll ans1=1; ///統(tǒng)計(jì) 此數(shù)為波峰 波浪數(shù)ll ans0=0; ///統(tǒng)計(jì) 此數(shù)為波谷 波浪數(shù)for (int j=0; j<m; j++){if (a[i]==b[j]) ///相等更新對(duì)應(yīng)波峰波谷的值{dp[0][j]+=ans1;///當(dāng)前數(shù)作為波峰接在波谷之后形成的波浪數(shù)dp[1][j]+=ans0;///當(dāng)前數(shù)作為波谷接在波峰之后形成的波浪數(shù)sum=(sum+ans1+ans0)%p; ///總情況數(shù)}else if(a[i]> b[j]) ///b小，可作為波谷接在波峰之后形成波浪{ans0+=dp[0][j];ans0%=p;}else{ans1+=dp[1][j]; ///b大，可作為波峰接在波谷之后形成波浪ans1%=p;}}}printf("%lld\n",sum);}return 0; }

ps：攢了一堆博客沒(méi)寫(xiě)嗚嗚嗚

總結(jié)

以上是生活随笔為你收集整理的HDU 6078 Wavel Sequence【动态规划】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。