題目鏈接

題意

? 對于一個數列 a1,a2,a3,...,an ，當且僅當 a1<a2>a3<a4>a5<a6... , b1,b2,b3,...,bm 。可以構建兩個新的數列 f1,f2,f3,...,fk , g1,g2,g3,...,gk 。問能構建多少個 f,g 滿足 afi=bgi 且 af1,af2,...,afk 是一個波浪。

分析

? 考慮枚舉A數列中取到位置 i 。B數列中取到了位置 j 。假設已知 cnt0 表示取 ai 之前，前一個值比 ai 高的種數，即以 ai 為波谷的種數， cnt1 為以 ai 為波峰的種數。那么如果 ai==bj ，對答案的貢獻為 cnt0+cnt1 。那么新的問題是如何快速求解 cnt0 和 cnt1 。設 sum[j][k] 表示 A 數列最多取到 i?1 , B 數列以位置 j 結尾，波峰波谷類型為 k 的種類數( k=1 表示波峰， k=0 表示波谷)。那么 cnt0=∑j?1t=1,bt>aisum[t][1],cnt1=∑j?1t=1,bt<aisum[t][0] 的過程中進行。對于 sum 數組的維護，顯然只有出現可行方案時需要更新，增加的方案為以 ai 為結尾的方案數，即對應的 cnt0,cnt1 。

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; #define MAXN 2020 #define eps 1e-7 #define lson rt<<1 #define rson rt<<1|1 #define LL long long const int mod=998244353; int a[MAXN]; int b[MAXN]; int sum[MAXN][2]; int main(){int T,n,m;cin>>T;while(T--){scanf("%d %d",&n,&m);memset(sum,0,sizeof(sum));for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=1;i<=m;++i)scanf("%d",&b[i]);int ans=0;for(int i=1;i<=n;++i){int cnt0=1,cnt1=0;for(int j=1;j<=m;++j){if(a[i]==b[j]){ans=(ans+(cnt0+cnt1)%mod)%mod;sum[j][1]=(sum[j][1]+cnt1)%mod;sum[j][0]=(sum[j][0]+cnt0)%mod;}else if(b[j]>a[i])cnt0=(cnt0+sum[j][1])%mod;elsecnt1=(cnt1+sum[j][0])%mod;}}printf("%I64d\n",ans);} }

總結

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

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