P9290

flangeborg · 2023-08-03 14:50:39 · 题解

前言

修改题解太痛苦了，还是麻烦审核大大了。

一道特别痛苦的单调栈 + dp 的问题、500ms 的时间限制真的赛神仙。本人也用了挺长时间，也去参考了其他 AC 大佬的做法，最后才把这道题 A 过了。

题目大意

给定一个长度为 n 的数组 a，一个合法序列的定义是：对于任意一个区间 [l,r]，区间的最小值为 a_l，最大值为 a_r。现在将这个长度为 n 的数组 a 分成 k 段，使得其中每一段都是合法序列，试求 k 最小值。

解题方法

• 看到“最小”、“最大”两个对于序列的限制，我们能够想到使用单调栈来维护数组。对于这道题我们需要用两个栈来维护。一个是严格单调递减的栈（stk1[n]），还有一个是单调递增的栈（stk2[n]）（关于为何使用这两种单调栈的问题建议配合后面的 AC 代码食用）。

• 其次，这道题还需要使用 dp 来求解。定义一个一维数组 dp[n]，对于任意一个数组下标 i，dp_i 表示到 i 坐标处，分割出来的序列全为合法序列的最小分割次数。

• 然后我们来构思状态转移方程，试想，如果当前坐标 i 后（注意是 i 坐标后，否则状态转移会出问题）需要进行分割以构成合法序列，上一次开始分割的坐标 j 需要尽可能地小才能保证转移出的结果是最小的。

• 有了这样的想法，这时候就应该与前面提到的单调栈来配合了。由于这道题对数组内的顺序有严格要求，所以这道题使用单调栈的时候，栈中存储的不是数组变量的值，而是数组变量的下标。

两个重要的结论及其证明：

1. 在严格单调递减栈中，在当前循环到第 i 次时，i 入栈，由于栈中的严格递减性，栈顶 i 所对应的 a_i 一定会小于栈中 i 下方（记为 j）所对应的 a_j ，并且通过单调性也可以得出 (j,i] 这个区间一定是合法的。

   证明：使用反证法，假设 (j,i] 区间为非法，则会至少有一个坐标 l 使得 a_l > a_i，则会使得当前递减栈除栈顶外第一个元素不是 j，出现矛盾，说明结论正确。

2. 在上一结论所描述的情况下，使用 STL 库中的 lower_bound 函数（意义及用法），以 j 为目标（即作为函数中的第三个参数）在单调递增栈中二分查找到的结果（即一个小于等于 j 的坐标，记为 p）在数组 a 中所对应的值 a_p 一定小于 a_j。

   证明：同样使用反证法，假设存在一个坐标 p 使得 a_p > a_j，因为 p < j，所以当 j 进入单调递增栈时，p 会被弹出栈，出现矛盾，说明结论正确。

状态转移方程

• 通过这些结论以及先前的构思推导，我们终于可以把这道题目中最重要的状态转移方程给列出来了，代码如下：

  dp[i]=dp[lower_bound(stk2+1,stk2+top2+1,stk1[top1-1])-1]+1;

• 经过如此长的思维历程才推出来的状态转移方程竟然如此简单，接下来上代码。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[300005],dp[300005],top1,top2,stk1[300005],stk2[300005];
//stk1：严格单调递减栈 stk2：单调递增栈（使用手写栈的原因是时间过于紧张） 
int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for(int i = 1; i <= n; i++)
    {
        while(top1 && a[stk1[top1]] <= a[i]) top1--;
        stk1[++top1] = i;
        while(top2 && a[stk2[top2]] > a[i]) top2--;
        stk2[++top2] = i;
        //维护两个单调栈 
        dp[i] = dp[*lower_bound(stk2 + 1,stk2 + top2 + 1,stk1[top1 - 1]) - 1] + 1;
        //千辛万苦得出的状态转移方程 
    }
    printf("%d",dp[n]);
    return 0;
} 

代码就到这了，希望能够对大家有所帮助。