HDU 6078 Wavel Sequence

xiaoxiao2021-02-28  70

/* LICS 变形 借鉴LICS 调整计算顺序,累计和,降低 dp 转移时的枚举量 。 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);++ i) #define IF if typedef long long ll; const int mod = 998244353; const int M =2e3+6; int a[M],b[M]; ll dp[M][2],sum[M][2]; int main() { int t,n,m; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); scanf("%d%d",&n,&m); rep(i,1,n) scanf("%d",&a[i]); rep(i,1,m) scanf("%d",&b[i]); ll ans=0; for(int i=1;i<=n;i++) { int cnt1=1,cnt0=0; for(int j=1;j<=m;j++) { IF(a[i]==b[j]) { dp[j][0]= cnt1; dp[j][1]= cnt0; sum[j][1] =(sum[j][1]+dp[j][1])%mod; sum[j][0] =(sum[j][0]+dp[j][0])%mod; ans =(ans+cnt1+cnt0)%mod; } IF(b[j]>a[i]) cnt1 =(cnt1+sum[j][1])%mod; IF(b[j]<a[i]) cnt0 =(cnt0+sum[j][0])%mod; } } printf("%lld\n",ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-78937.html

最新回复(0)