P4063 [JXOI2017] 数列
题意
给定长度为 \(n\) 的整数数列 \(r_i\)，构造长度为 \(n\) 的序列 \(A\) 的规则如下：
-
\(1 \le A_i \le r_i\)。
-
对于任意 \(3 \le i \le n\)，令 \(R\) 为 \(A_1\) 至 \(A_{i-2}\) 中大于等于 \(A_{i-1}\) 的最小值，\(L\) 为 \(A_1\) 至 \(A_{i-2}\) 中小于等于 \(A_{i-1}\) 的最大值。\(A_i\) 必须满足 \(L \le A_i \le R\)。如果不存在大于等于 \(A_{i-1}\) 的，那么 \(R=+\infty\)；如果不存在小于等于 \(A_{i-1}\) 的，那么 \(L = -\infty\)。
请求出可以构造出多少种不同的序列 \(A\)。
\(n\le 50,r_i\le 150\)。
题解
知识点：动态规划。
小水题。
设出状态 \(dp_{i,l,r,x}\) 表示当前选到第 \(i\) 个，第 \(i-1\) 个选的是 \(x\)，且满足 \(L=l,R=r\)。
定义状态为一个三元组 \((l,r,x)\)，它会经历若干个形如 \((l,r,x)\to (l',r',x')\) 的过程，这个过程中从 \([l,r]\) 到 \([l',r']\)，区间只会不断缩小，这是容易证明的。
显然有 \(l\le x\le r\)。
设当前选了数 \(y\)，则有以下几个转移的可能：
\((l,r,x)\to (y,y,y)\)，当且仅当 \(y\) 等于 \(l,r,x\) 中任意一个，说明前面存在即 \(\ge y\) 又 \(\le y\) 的数，那么就是 \(y\)。
\((l,r,x)\to (x,r,y)\)，当且仅当 \(y>x\)。
\((l,r,x)\to (l,x,y)\)，当且仅当 \(y<x\)。
到这里已经可以写出朴素的 dp 转移了，时间复杂度 \(O(nv^4)\)，不足以通过此题。
考虑优化，发现第一种转移只会有常数次，第二种和第三种的转移范围都是一个区间，所以可以在 dp 数组上作差分以区间加，最后在做一遍前缀和即可，时间复杂度 \(O(nv^3)\)，勉强能过。
至于 dp 的初始状态，枚举前两个数的取值即可。
#include<bits/stdc++.h>
using namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()#define N 55
#define V 155
#define int long longconst int mod=998244353;
int n,a[N],f[V][V][V],g[V][V][V],s[V][V][V];inline void add(int &x,int y){x=(x+y+mod)%mod;
}signed main(){// freopen(".in","r",stdin);// freopen(".out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;int lim=0;rep(i,1,n){cin>>a[i];lim=max(lim,a[i]);}lim++;rep(i,1,a[1]){rep(j,1,a[2]){if(i<j){f[i][lim][j]=1;}else if(i>j){f[0][i][j]=1;}else{f[i][i][i]=1;//spec}}}rep(i,3,n){memset(g,0,sizeof g);memset(s,0,sizeof s);rep(l,0,lim-1){rep(r,max(1ll,l),lim){rep(k,max(1ll,l),min(r,a[i-1])){if(!f[l][r][k]){continue;}int re=f[l][r][k];vector<int>sp={l,k,r};sp.erase(unique(all(sp)),ed(sp));for(int x:sp){if(x<1||x>a[i]){continue;}add(g[x][x][x],re);// cout<<x<<' '<<x<<' '<<x<<" add1\n";}if(l+1<=k-1){add(s[l][k][l+1],re);add(s[l][k][k],-re);}if(k+1<=r-1){add(s[k][r][k+1],re);add(s[k][r][r],-re);}}}}rep(l,0,lim-1){rep(r,max(1ll,l),lim){rep(k,1,max(1ll,l)-1){add(s[l][r][k],s[l][r][k-1]);}rep(k,max(1ll,l),min(r,a[i])){add(s[l][r][k],s[l][r][k-1]);add(g[l][r][k],s[l][r][k]);}}}memcpy(f,g,sizeof g);}int ans=0;rep(i,0,lim){rep(j,0,lim){rep(k,0,lim){// cout<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<"\n";ans=(ans+f[i][j][k])%mod;}}}cout<<ans;return 0;
}