#C231028B. 排列(per)
标签（Label）
- 动态规划
- 前缀和优化
网址（Website）
题目（Problem）
给定一个长度为 $n$ 的排列 $p$ 。小 $\mathrm{M}$ 会进行以下操作 $n$ 次:
- 将当前 $p$ 序列的最小值加入 $a$ 序列末尾。
- 从 $p$ 序列的开头或者末尾删去一个数。
小 $\mathrm{M}$ 想知道能得到几种不同的 $a$ 序列, 请你帮帮他。输出答案对 $998244353$ 取模后的结果。
对于 $100 %$ 的数据, $1 \leq n \leq 5000$ 。
题解（Solution）
$\qquad$这道题会出现严重的读题错误（bushi），我直接把它的一个操作的两个步骤看成了一个操作选任意一个操作，现在补题的时候才发现。
$\qquad$按题解来说，考虑一件事情：如果对于当前区间 $[l,r]$ 中有最小值 $p_x$ ，那么要想使 $a_i$ 中出现 $p_i\ (i\in [x+1,r] )$ ，就必须将 $[l,x]$ 的所有数全部删去，而若在删左边的过程中删除了右边的数，则会增加 $p_x$ 在 $a_i$ 中出现的次数。想要使 $p_i\ (i\in [l,x-1])$ 出现也是一个道理。如果想让后边只有 $p_x$ 出现，那么需要删掉左右两边的所有数。
$\qquad$于是乎，这道题就转化为一道 $dp$ 题： 设 $d p_{l, r}$ 表示当前区间 $[l, r]$ 中区间最小值为 $p_{x}$ ，且满足 $a$ 的最后一个元素在区间外 ， $dp_{l,r}=\sum_{l=i}^{i\le x-1}{dp_{i,x-1}}+\sum_{i=x+1}^{i\le r}{dp_{x+1,i}}+1$ 。前缀和优化后可以做到 $O(n^2)$ 。
$\qquad$而我最大的问题就是难以对这类 $dp$ 题目求出方程。
代码（Code）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
inline int input(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
const int mod = 998244353;
const int N = 5005;
pair<int,int> mn[N][24];
int n,a[N];
int dp[N][N],sl[N][N],sr[N][N];
inline pair<int,int> ask(int l,int r){
int k=__lg(r-l+1);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
inline void trans(int l,int r){
int minn=ask(l,r).second;
dp[l][r]=(1ll*sl[minn+1][r]+sr[l][minn-1]+1)%mod;
sl[l][r]=(1ll*sl[l][r-1]+dp[l][r])%mod;
sr[l][r]=(1ll*sr[l+1][r]+dp[l][r])%mod;
}
signed main(){
freopen("per.in","r",stdin);
freopen("per.out","w",stdout);
n=input();For(i,1,n) a[i]=input(),mn[i][0]={a[i],i};
for(int j=1;j<=18;j++)//预处理 ST 表
for(int i=1;i+(1<<j)-1<=n;i++)
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
Rof(i,n,1) For(j,i,n) trans(i,j);
return printf("%lld",dp[1][n]),0;
}后续（Ending）
$\qquad$终于把题解上的错误改过来了，同时也加深了自己的理解。
$\qquad$对于 $\sum_{l=i}^{i\le x-1}{dp_{i,x-1}}$ ，可以理解为：此时要删去所有的 $p_i\ (i\in [x,r])$ ，而正如上文所说的“控制 $p_x$ 的个数”，因此删完右边后左边区间可能一个没删、删了一个、删了两个······或者删来只剩一个，那么贡献自然是这些数加起来。
$\qquad$对于 $\sum_{i=x+1}^{i\le r}{dp_{x+1,i}}$ ，理解是一样的。
$\qquad$而对于最后的 $+1$ ，其实是代表当前区间左右都删了，只剩下 $p_x$ 的情况。
$\qquad$再考虑计算转移的优化，我们可以从左往右考虑，那么内层循环直接累积一个 $suml$ 就可以得到从 $l$ 到当前的 $i$ 的和，同时，外层循环可以从最右边求到最左边，累计一个$sumr$，那么最小值一定在已经记录的 $sumr$ 数组里面，那么 $dp[1][n]$ 就是最终的答案。
$\qquad$本题还有卡常的问题，注意要用__lg()函数，不要用log2()函数，否则时间会大量延长。（总时间延长 $3200ms$ 左右）
