Description 定义波浪序列：a1 > a2 < a3…，现在给出一个长度为n的序列a和一个长度为m的序列b，求a和b的公共波浪子序列个数 Input 第一行一整数T表示用例组数，每组用例首先输入两个整数n和b表示两个序列的长度，然后输入一个长度为n的序列a[1]~a[n]和一个长度为m的序列b[1]~b[m] (1<=T<=15,1<=n,m,a[i],b[j]<=2000) Output 输出a和b的公共波浪子序列个数 Sample Input 1 3 5 1 5 3 4 1 1 5 3 Sample Output 10 Solution Code
#include<cstdio> #include<cstring> using namespace std; const int maxn=2001,mod=998244353; namespace fastIO { #define BUF_SIZE 100000 //fread -> read bool IOerror=0; inline char nc() { static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if(p1==pend) { p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if(pend==p1) { IOerror=1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch==' '||ch=='\n'||ch=='\r'||ch=='\t'; } inline void read(int &x) { char ch; while(blank(ch=nc())); if(IOerror)return; for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0'); } #undef BUF_SIZE }; using namespace fastIO; int T,n,m,a[maxn],b[maxn],dp[maxn][2],sum[maxn][2]; int inc(int x,int y) { return x+y>=mod?x+y-mod:x+y; } int main() { read(T); while(T--) { read(n),read(m); for(int i=1;i<=n;i++)read(a[i]); for(int i=1;i<=m;i++)read(b[i]); memset(sum,0,sizeof(sum)); int ans=0; for(int i=1;i<=n;i++) { int num0=0,num1=1; for(int j=1;j<=m;j++) { dp[j][0]=dp[j][1]=0; if(a[i]==b[j]) { dp[j][0]=num1,dp[j][1]=num0; ans=inc(ans,inc(num0,num1)); } else if(a[i]<b[j])num1=inc(num1,sum[j][1]); else num0=inc(num0,sum[j][0]); } for(int j=1;j<=m;j++) sum[j][0]=inc(sum[j][0],dp[j][0]),sum[j][1]=inc(sum[j][1],dp[j][1]); } printf("%d\n",ans); } return 0; }