CF1868E 题解

## 题意 给定一个序列 $a$ 的 $n$ 个元素 $a_i$（$a_i$ 可能为负）。把序列 $a$ 划分成 $k$（$k\ge 1$） 个区间（区间互不相交，区间并为 $a$），分别为 $[l_1=1,r_1],[l_2=r_1+1,r_2]....[l_k=r_{k-1}+1,r_k=n]$，记 $s_i=\sum_{j=l_i}^{r_i}a[j]$，若满足以下条件，则称这个划分是合法的： $$ \forall 1\le i\le j\le k,\min_{i\le l \le j}(s_l)\le \sum_{l=i}^{j}s_i\le \max_{i\le l \le j}(s_{l}) $$ 现在询问你一个最大 $k$ 满足存在一个合法的 $k$ 个区间的划分。多测 $n\le 300,\sum n\le 1000,-10^9\le a_i\le10^9$。 ## 题解 一眼丁真，鉴定为 DP。问题就在于怎样划分状态——找性质。 先起手一个前缀和，即 $S_i=\sum_{j=1}^{i}a_i$。问题转化为给你序列 $S_0 ...S_n$，让你选择 $k+1$ 个数 $r_1\le r_2\le ... \le r_{k+1}\in[0,n]$，并满足下列条件： $$ \forall 1\le i<j\le k,\min_{i< l\le j}(S_{r_l}-S_{r_{l-1}})\le S_{r_i}-S_{r_{j}}\le \max_{i<l\le j}(S_{r_l}-S_{r_{l-1}}) $$ 那么我们肯定是希望 $\min$ 尽量小，$\max$ 尽量大，并且最好确定确定取值。一个（一定）可能是答案的思路是考虑一手最大值和最小值。 我们发现当 $S_{r_i}$ 是最大值，$S_{r_j}$ 是最小值的时候，$S_{r_i}-S_{r_j}$ 一定是全局 $S_{p}-S_{q}$ 中最大的一个，其中 $p,q\in[0,n]$。即 $\max_{i<l\le j}(S_{r_l}-S_{r_{l-1}})=S_{r_i}-S_{r_j}$。那么要不然在 $i$ 和 $j$ 中间至少还选择了一个最小值或最大值，要么满足他自身贡献了 $\max$——即最大值和最小值在我们选择的数中相邻。而对于前一种情况（中间至少还选择了一个最小值或最大值），我们可以令新的 $i$ （或 $j$） 等于在 $i$ 和 $j$ 中间的一个任意最大值（或最小值）所在的位置。由于区间长度严格减小，因此一定会归纳到第二种情况。显然，当 $S_{r_i}$ 为最小值，$S_{r_j}$ 为最大值的情况也是同理。 即在我们选择的序列 $r$ 中，其中一个最大值和最小值一定相邻。容易想到枚举这个最大值（设为 $i+1$）和最小值（设为 $i$）。接着一个很自然的想法就是他们能把序列 $r$ 分成 $r_1...r_i$ 和 $r_{i+1}....r_{k+1}$ 两部分，并且计算互不干扰。证明就很 naive 了： * 假设仅考虑区间 $[r_{i+1},n]$ 和 $\forall l \in [i+1,j],r_{l}...r_{j}$ 满足条件。我们断言 $\forall l \in [1,i],r_l...r_j$ 都满足条件（此处的满足条件指的是在题目中 $j$ 固定为我上文写的 $j$）： * 我们先考虑序列 $r_i...r_j$，注意到此时最大值为 $S_{r_{i+1}}-S_{r_i}$，因此一定满足 $\max$ 的限制。而对于最小值的限制来说，由于 $\min_{i+1<l\le j}(S_{r_l}-S_{r_{l-1}})\le S_{r_j}-S_{r_{i+1}}$，并且 $S_{r_{i+1}}\ge S_{r_i}$ 和 $\min_{i<l\le j}(S_{r_l}-S_{r_{l-1}})\le \min_{i+1<l\le j}(S_{r_l}-S_{r_{l-1}})$，所以: $$ S_{r_j}-S_{r_{i}}\ge S_{r_{j}}-S_{r_{i+1}}\ge \min_{i+1<l\ge j}(S_{r_l}-S_{r_{l-1}})\ge \min_{i<l\le j}(S_{r_l}-S_{r_{l-1}}) $$ * 因此 $r_i...r_j$ 满足条件，又注意到 $S_{r_j}-S_{r_{i}}$ 和 $S_{r_j}-S_{r_{i+1}}$ 分别取到 $S_{r_j}-S_{l}$ 的极值，其中 $l\in [0,n]$。又因为 $\min$ 和 $\max$ 随着 $r_l....r_j$ 中 $l$ 的减小分别减小和增大。即限制区间不断变宽，但中间的数却没有变得更大和更小。因此仍然合法。 * 反一反也是同理。那么接下来对于满足题目条件的序列 $r_{1}...r_{k+1}$，对每个 $\forall l \in [1,k+1]$ 分别运用上述结论进行扩展即可。 我们就有一个不成熟的 DP 了： > 设 $dp_{i,j,l,r}$ 表示区间 $[i,r]$，选的数必须满足在区间 $[l,r]$，在如上方式的选法之下，选的最大个数。初值为 $dp_{i,i,S_i,S_i}=1$。更新如下： $$ \forall i\le x,y \le r,l \le S_x,S_y \le r $$ $$ dp_{i,j,l,r} \leftarrow dp_{i,x,\min(S_x,S_y),\max(S_x,S_y)}+dp_{y,j,\min(S_x,S_y),\max(S_x,S_y)} $$ $$ dp_{i,j,l,r} \leftarrow dp_{i,j,l,r-1} $$ $$ dp_{i,j,l,r} \leftarrow dp_{i,j,l+1,r} $$ 显然复杂度为 $O(n^6)$，但题解说二维前缀 $\max$ 肯定优化成 $O(n^4)$,但我没有悟到。 接下来考虑优化 DP。注意到每次更新后 $dp_{i,j,l,r}$ 中 $S_i$ 和 $S_j$ 中的一个肯定取到 $l,r$ 中的一个。那么 DP 状态可以先优化到 $O(n^3)$，但我们还是沿用之前的 DP 进行讨论。 在接下来的讨论中，我们假设 $S_i$ 取到 $l$。但怎么优化呢？  （he 张 DX 的图片。） 我们发现我们的检查算法描述如下：每次找到一条边（指一对 $(S_{r_i},S_{r_{i+1}})$）满足两边的端点在值为 $l,r$ 的情况下最大和最小。然后分成两半检查。我们发现每条边都会被检查一遍。 所以，在 $dp_{i,j,l,r}$ 中，显然若 $i\not =j$，点 $i$ 在此时只连了一条边。显然另一条边必须连上。即在连另一条边之前，必须始终满足 $l\le i \le r$ 。又因为 $l=i$。因此在 $i$ 被选择之前，必须满足 $l = i$。也就是说当 $i$ 还存在于这个区间时，枚举的最小值必须等于 $S_i$。 有了这个关键的观察过后狗都会做了。这里说一种简单的实现方法。以 $S_i=l$ 的情况为例。由于枚举的最小值等于 $S_i$。我们只需要枚举最大值（设为 $x$）即可。显然在枚举最大值之后我们应该取他左边第一个等于 $S_i$ 的位置 $y_1$ 和右边第一个等于 $S_i$ 的位置 $y_2$。那么转移如下：初值为 $dp_{i,i,S_i,S_i}=1$ $$ \forall i\le x,y \le r,l \le S_x,S_y \le r $$ $$ dp_{i,j,S_i,r} \leftarrow dp_{i,y_1,S_i,S_x} +dp_{x,j,S_i,S_x} $$ $$ dp_{i,j,S_i,r} \leftarrow dp_{i,x,S_i,S_x} +dp_{x,y_2,S_i,S_x} $$ $$ dp_{i,j,S_i,r} \leftarrow dp_{i,j,S_i,r-1} $$ 下面是 $x$ 取到最小值的情况： $$ dp_{i,j,l,S_i} \leftarrow dp_{i,y_1,S_x,S_i}+dp_{x,j,S_x,S_i} $$ $$ dp_{i,j,l,S_i} \leftarrow dp_{i,x,S_x,S_i}+dp_{y_2,j,S_x,S_i} $$ $$ dp_{i,j,l,S_i} \leftarrow dp_{i,j,l+1,S_i} $$ 另外，你发现在上面的转移中左边的点的值始终取到 $l,r$ 中的一个，因此可以设 $f_{i,j,k,0}$ 表示 $dp_{i,j,k,S_i}$ 和 $f_{i,j,k,1}$ 表示 $dp_{i,j,S_i,k}$ 轻松转移。 另外注意一下，由于 DP 中的 $k$ 记录的是和 $i$ 相关的信息，因此要确保算答案时枚举的端点 $x,y$ 都是 DP 的左端点。这个可以通过翻转做两次 DP 实现。 代码实现如下： ``` #include<bits/stdc++.h> #define ll long long using namespace std; const int N=350,inf=1e9; int n; int f[N][N][N][2],g[N][N][N][2]; int s[N],id[N],val[N]; ll a[N],b[N]; void cmx(int&x,int y){x=max(x,y);} void work(auto&f) { for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=b[0];k++)f[i][j][k][0]=f[i][j][k][1]=-inf; for(int i=n;i>=0;i--) { static int pre[N],suf[N]; memset(pre,-1,sizeof(pre));memset(suf,-1,sizeof(suf)); for(int j=i,now=-1;j<=n;j++) { if(i==j)f[i][j][s[j]][0]=f[i][j][s[j]][1]=0; //这里跟题解所说的不一样。每次合并是贡献 + 1 恰好是所选的个数 -1，即恰好是答案（区间个数） else for(int k=i;k<=j;k++) { if(s[k]>=s[i]) { if(k>0&&pre[k-1]!=-1)cmx(f[i][j][s[k]][1],f[i][pre[k-1]][s[k]][1]+f[k][j][s[i]][0]+1); if(suf[k+1]!=-1)cmx(f[i][j][s[k]][1],f[i][k][s[k]][1]+f[suf[k+1]][j][s[k]][1]+1); } if(s[k]<=s[i]) { if(k>0&&pre[k-1]!=-1)cmx(f[i][j][s[k]][0],f[i][pre[k-1]][s[k]][0]+f[k][j][s[i]][1]+1); if(suf[k+1]!=-1)cmx(f[i][j][s[k]][0],f[i][k][s[k]][0]+f[suf[k+1]][j][s[k]][0]+1); } } if(j)pre[j]=pre[j-1]; if(s[j]==s[i]){pre[j]=j;for(int k=j;k>now;k--)suf[k]=j;now=j;} for(int k=2;k<=b[0];k++)f[i][j][k][1]=max(f[i][j][k][1],f[i][j][k-1][1]); for(int k=b[0]-1;k>=1;k--)f[i][j][k][0]=max(f[i][j][k][0],f[i][j][k+1][0]); } } } signed main() { int _;scanf("%d",&_); while(_--) { scanf("%d",&n);b[0]=0;s[0]=0;a[0]=0; for(int i=1;i<=n;i++)scanf("%d",&s[i]),(a[i]=s[i]+a[i-1]),b[++b[0]]=a[i]; b[++b[0]]=0;sort(b+1,b+b[0]+1);b[0]=unique(b+1,b+b[0]+1)-b-1; for(int i=0;i<=n;i++)s[i]=lower_bound(b+1,b+b[0]+1,a[i])-b; work(f);reverse(s,s+n+1);work(g);reverse(s,s+n+1); int ans=1; for(int x=0;x<n;x++)for(int y=x+1;y<=n;y++) ans=max(ans,g[n-x][n][s[y]][s[y]>=s[x]]+(f[y][n][s[x]][s[x]>s[y]])+1); printf("%d\n",ans); } return 0; } ``` ## 后记   说点个人看法。我感觉这道题 的 idea 很棒，hack 数据放第二组 pretest 感觉跟出题人脚造大大样例的恶臭程度差不多。感觉比 CF 放 Hash 题 和初赛试卷快读和树状数组写错的程度稍逊一筹。  但是，喷完了，然后呢？因低素质行为而退役的选手数不胜数，即便现在有人尝试去[改革](https://www.cnblogs.com/mathematician/p/17644492.html)，但不多。 我们能做什么呢？少说，多做，明哲保身。“个人奋斗固然重要，也不能忽略时代的进程”。 另外 DX 怒喷 CF 题解看不懂。主要是因为 CF 题解证明都漏光了（像我是先学习代码再悟的）。那你写题解也写点证明好伐，就算配了图以我这样的智商也看不懂。 另外在这里问一句：“合法的单调栈进出序列”是嘛意思，我悟不到啊。 另外再吐槽一句，“证明很简单，如果有人在评论区问了我就写一下吧。”感觉这话跟我发誓要写回家作业一样，是一种量子力学。