【題目鏈接】http://acm.hdu.edu.cn/showproblem.php?pid=6078

題目意思

給定兩個數(shù)組問你同時滿足波浪的波浪數(shù)。不理解可以看題目提示部分

解題思路

首先從a數(shù)組一個個往下查詢b數(shù)組是否有相同數(shù)字。在查詢新的數(shù)字時候就要判斷前面是否有可以與新加的數(shù)字組成波浪的，而當(dāng)新加數(shù)比前面的數(shù)大時候就可以添加前面數(shù)字為波谷的情況下，而自己添加后處在波峰的位子（如前面有的1 3，現(xiàn)在加入5的話就會考慮15和53的情況，這時候1和3處在波谷而5處在波峰）反之波谷。所以開二維數(shù)組dp來存儲的處在波峰的情況個數(shù)和波谷的個數(shù)。。。又因?yàn)閍數(shù)組可能有相同數(shù)字出現(xiàn)所以開s二維數(shù)組儲存之前的狀況。具體如代碼

代碼部分

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll p=998244353; //const LL MAXN=1e6+10; int a[2005],b[2005]; ll dp[2][2005],s[2][2005];///dp數(shù)組存本輪的值，s數(shù)組存儲總次數(shù)的（防止a數(shù)組出現(xiàn)相同數(shù)字） int main() {int t;scanf("%d",&t);while (t--){int n,m;ll sum=0;memset(dp,0,sizeof(dp));memset(s,0,sizeof(s));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ì)為前面波谷的情況，同時自己屬于波峰ll ans0=0; ///統(tǒng)計(jì)為前面波峰的情況，自己屬于波谷for (int j=0; j<m; j++){if (a[i]==b[j]) ///相等更新對應(yīng)波峰波谷的值{dp[0][j]=ans1; ///波峰dp[1][j]=ans0; ///波谷sum=(sum+ans1+ans0)%p; ///總情況數(shù)}else if(a[i]> b[j]) ///a[i]比b[j]打所以b可以嫁接a處在波峰的情況ans0+=s[0][j]%=p;else ans1+=s[1][j]%=p; ///反之嫁接波谷的情況}for (int j=0; j<m; j++) {if (a[i]==b[j]) ///把之前的a[i]的次數(shù)加上本輪的{s[0][j]+=dp[0][j]%=p; s[1][j]+=dp[1][j]%=p;}}}printf("%lld\n",sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 6078Wavel Sequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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