题意：
给出两个长度为n的序列a , b构造一个序列c满足a i < = c i < = b i并且c非单调递减。求方案数。n < = 3000 , 0 < = a i , b i < = 3000
思路：
数据范围比较小，考虑d p
记d p [ i ] [ j ]表示选完了前i个数并且第i个数的值为j的方案数。
转移有d p [ i ] [ j ] = ∑ d p [ i − 1 ] [ k ] , a i − 1 < = k < = j
用前缀和优化一下，记s u m [ i ] [ j ]表示选了i个数并且第i个数的值< = j的方案数。
转移就变成了d p [ i ] [ j ] = s u m [ i − 1 ] [ j ] − s u m [ i − 1 ] [ a [ i − 1 ] − 1 ]
有几个小细节：
第i − 1层的s u m只维护到了b i − 1，所以如果j > b i − 1 的话，是没有值的，应该取m i n ( j , b i − 1 ) a i , b i都是可以为0 的话，如果为0的话，a [ i − 1 ] − 1就会变成− 1，但是不能跟0 取m a x，不然就会漏掉0的部分。我的处理方式是在输入的时候让所有的a , b都增加1,这样不会影响相对大小，下标也不是− 1
代码：
// Problem: D - Between Two Arrays // Contest: AtCoder - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） // URL: https://atcoder.jp/contests/abc222/tasks/abc222_d // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7; const ll mod=998244353; ll dp[3100][3100],n,a[3100],b[3100]; ll sum[3100][3100]; int main(){ n=read; rep(i,1,n) a[i]=read+1; rep(i,1,n) b[i]=read+1; for(int i=a[1];i<=b[1];i++) dp[1][i]=1,sum[1][i]=sum[1][i-1]+dp[1][i]; for(int i=2;i<=n;i++) for(int j=a[i];j<=b[i];j++){ if(j>=a[i-1]) dp[i][j]=(dp[i][j]+sum[i-1][min(j*1ll,b[i-1])]-sum[i-1][max(0ll,a[i-1]-1)]+mod)%mod; sum[i][j]=(sum[i][j-1]+dp[i][j])%mod; } ll ans=0; for(int i=a[n];i<=b[n];i++) ans=(ans+dp[n][i])%mod; cout<<ans; return 0; }
