題

　　OvO?http://acm.hdu.edu.cn/showproblem.php?pid=6078

　　(2017 Multi-University Training Contest - Team 4?- 1012)

解

　　記f[i][j][k]為在s1中以第i位結(jié)尾，s2中以第j為結(jié)尾，末端狀態(tài)（上升為1，下降為0）為k的子序列的個數(shù)

　　則f[i][j][k]=∑f[p][q][1-k] ?(p<i,q<j，而且新加入的點要使原序列結(jié)尾狀態(tài)發(fā)生變化)　

　　可見這是和矩陣差不多的東西

　　可以把這個當做一個矩形，s1豎著，s2橫著

　　然后用類似前綴和的思想來優(yōu)化　

　　有2個數(shù)組用于優(yōu)化

　　fx[i][j][k]代表，狀態(tài)k時，第1~i行，第j列的綜合，即第j列的前綴。每當(i,j)處產(chǎn)生新方案的時候，都要往(i+1,j)處更新

　　fy[i][j][k]比較特殊，代表狀態(tài)k時，第i行第j列可行的方案數(shù)量，也就是可以直接用于(i,j)點更新的方案數(shù)量。

　　fy的數(shù)組的更新的話

　　1.對于同一行的fy[i][j][k]直接向后推至fy[i][j+1][k]處

　　2.對于fx[i][j][k]中的方案，如果合法，則放入該行的fy[i][j+1][k]中。

　　　　對于合法的判斷，由于fx[i][j][k]中的方案，對于s2上的數(shù)，是以s2[j]結(jié)尾的，而當前這一行的要更新的點，對應(yīng)的是s1[i]。也就是說根據(jù)k的值將兩者比較就可以判斷是否合法。

　　維護這兩個數(shù)組，如果當前點s1[i]==s2[j]就代表可以把fy中預(yù)備著的值（實質(zhì)上是一個二維的前綴和）加入到答案中來。每次更新答案都會產(chǎn)生新的序列，要把這個序列的數(shù)量放到fx中。

　　（思路來自csy的標程與題解）

?

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring>using namespace std;typedef long long ll;const int M=2044; const ll mod=998244353;int n,m; ll fx[M][M][2],fy[M][M][2];//if the tail of is up 1, otherwise 0 int s1[2222],s2[2222];void init() {memset(fx,0,sizeof(fx));memset(fy,0,sizeof(fy)); }void solve() {//regard it as a matrix//s1 row ; s2 colint i,j,k;ll ans=0,tmp;for(i=1;i<=n;i++) //row for(j=1;j<=m;j++) //colfor(k=0;k<=1;k++){if(s1[i]==s2[j]) //new seq{tmp=fy[i][j][1-k];if(k)tmp++;if(tmp){ans=(ans+tmp)%mod;fx[i+1][j][k]=(fx[i+1][j][k]+tmp)%mod; //push up the num of new seq}}//fx push upfx[i+1][j][k]=(fx[i+1][j][k]+fx[i][j][k])%mod;if((k && s1[i]>s2[j]) || (!k && s1[i]<s2[j])) //if the fx have affect on this rowfy[i][j+1][k]=(fy[i][j+1][k]+fx[i][j][k])%mod;//fy push upfy[i][j+1][k]=(fy[i][j+1][k]+fy[i][j][k])%mod;}cout<<ans<<endl; }int main() {int T,i,j;cin>>T;while(T--){init();scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&s1[i]);for(i=1;i<=m;i++)scanf("%d",&s2[i]);solve();}return 0; }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/FxxL/p/7281970.html

總結(jié)

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

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