Wavel Sequence

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 a1a3a5

#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int max_n=2009; const int mod=998244353; int a[max_n],b[max_n]; int n,m,num0,num1,ans; int once[max_n][2],sum[max_n][2];///once是指以b數組中此次狀態下的的第i為作為谷態(0)和峰態(1)的個數///sum是指以b數組中之前所有的的第j位作為谷態(0)和峰態(1)的個數 int main() {int T;scanf("%d",&T);while(T--){ans=0;memset(sum,0,sizeof(sum));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]);for(int i=1;i<=n;i++){num0=1;///表示此次作為波谷的個數，因為最開始的那個肯定要從波谷開始num1=0;///表示此次作為波峰的個數for(int j=1;j<=m;j++){if(a[i]==b[j])///兩個相同的話，則進行狀態的轉移{once[j][0]=num0;once[j][1]=num1;ans=(ans+(once[j][0]+once[j][1])%mod)%mod;}if(a[i]>b[j])///這里作為波峰{num1=(num1+sum[j][0])%mod;///這次的可以作為波峰的加上之前的波谷}if(a[i]<b[j]){num0=(num0+sum[j][1])%mod;///這次的可以作為波谷的加上之前的波峰}}for(int j=1;j<=m;j++){if(a[i]==b[j]){sum[j][0]=(sum[j][0]+once[j][0])%mod;sum[j][1]=(sum[j][1]+once[j][1])%mod;}}}printf("%d\n",ans);}return 0; }

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。