题解 P6563 【[SBCOI2020] 一直在你身旁】

· · 题解

题目链接

这道题题解写的太简洁了，这个 蒟蒻 看的很费劲，于是他决定写一篇更详细一点的题解。

基础分析：

基础 DP 方程：

\large dp[l][r] = \min\limits_{l\leq k<r}(\max(dp[l][k],dp[k+1][r])+a[k])

这个式子还是很难理解的（也可能是我太菜了）。

首先是 dp[l][r] 的定义：确定电线长度在 [l,r] 后最少需要多少钱才能准确确定电线长度。

显然当区间 l == r 时，dp[l][r] 的值为 0 。

此时，我们就可以逆推，从确定的元区间 [l,l] 向上转移，从而推出 dp[l][r] ，转移就是上述方程（状态设计好了，转移还是比较容易的）。

但朴素做法是 O(n^3) 级别的，本题过不了。

优化：

看了一眼暴力的 DP 的式子，感觉有点单调队列优化的感觉，可以试一下：

但是这个方程 \min\limits_{i<k<j}(\max(dp[l][k],dp[k+1][r])+a[k]) 很恶心，套了个 \min\max ，不好直接搞。

先考虑 l,r 已固定的情况。

仔细观察，在 k 移动的过程中，dp[l][k] 是单调不减的， dp[k+1][r] 是单调不增的，这一点还是比较好想的。

然后转换一下即是：当 dp[l][k] > dp[k+1][r] 时，后面 max 的决策一定是选择 dp[l][k] ，且在往后决策也不会变，反之选择dp[k+1][r] 。

于是我们总算有一点眉目了，即对每一个区间 [l,r] 都存在一个中转点 x 满足 k < x 时选择 dp[l][k] ,反之选择 dp[k+1][r] 。

接下来继续考虑 l,r 移动的情况。

我们移动区间 [l,r] 时，此时我们主要思考一下的是中转点 x 的位置的变化,设 x_{l,r} 表示区间 l,r 的中转点。

肯定的是它的位置是单调的，也即对于任意区间 [l,r],[l+k_1,r+k_2],k_1,k_2\in\N^+ 都满足 \Large x_{l+k_1,r+k_1} > x_{l,r}。

列一下表就可以得到：

我自己都不是很明白为什么要把那么显然的一个东西分类讨论,可能因为我是个蒟蒻。

综上，我们可以确定中转点是具有单调性。

进一步分析，当中转点确定时，dp[l][r] 可能的取值。

很明显，它是需要分类讨论。

这一个式子根据上面 dp[l][k] 是单调不减的，所以最小的直接取 dp[l][r] = dp[l][k]+a[k] 即可。

这一个式子是满足单调性的，可以直接普通单调队列维护。

综上，我们成功将时间复杂度优化到了 O(n^2)，本题可以过。

代码实现：

下面贴的代码省略了前面漫长的手写 IO ，转移方面借鉴了 JohnVictor 大佬的提供的优化，将 l,r 换了个位置。

# define N 7100
# define reg register

class ysys_Deque 
{
    private:
            int d_e_q_u_e[(N<<1) + 5],Rear_,Front_;

    public :
            ysys_Deque(){Rear_=N;Front_=N+1;}
            ~ysys_Deque(){}

            inline bool Empty(){return Front_ > Rear_;}
            inline int Size(){return Front_ <= Rear_ ? Rear_-Front_+1 : 0;}
            inline void Reset(){Rear_=N;Front_=N+1;} 
            inline int Front(){return d_e_q_u_e[Front_];}
            inline int Rear(){return d_e_q_u_e[Rear_];}
            inline int Get_Back(){return d_e_q_u_e[Rear_--];}
            inline int Get_Front(){return d_e_q_u_e[Front_++];}
            inline void Pop_Back(){--Rear_;}
            inline void Pop_Front(){++Front_;}
            inline void Push_Front(const int Val){d_e_q_u_e[--Front_] = Val;}
            inline void Push_Back(const int Val){d_e_q_u_e[++Rear_] = Val;}

} q;//手写双端队列

using namespace ysys::MMS;
long long f[N+5][N+5],a[N + 5];
int n,T;
using namespace ysys::unsigned_IO_f;

int main()
{
    T = Read();

    while(T--)
    {
        n = Read();

        for(reg int i = 1; i <= n ; ++i) a[i] = ReadL();

        for(reg int r = 2;  r <= n ; ++r)
        {//如果枚举区间长度，，改为枚举右端点。
            q.Reset();q.Push_Back(r-1);

            f[r][r-1] = a[r-1];

            for(reg int l = r-2,k = r; l ; --l)//倒序枚举便于对右区间选取。
            {
                while(f[k-1][l] > f[r][k] && l < k) --k;//寻找中转点。

                f[r][l] = f[k][l] + a[k];//取dp[l][k]的转移。

                while(q.Size() && k <= q.Front()) q.Pop_Front();//将小于了中转点 k 的dp[k+1][r] 出队。

                if(q.Size()) f[r][l] = Min(f[r][l],f[r][q.Front()+1] + a[q.Front()]);

                while(q.Size() && f[r][q.Rear()+1] + a[q.Rear()] >= f[r][l+1] + a[l]) q.Pop_Back();
                //新增加的可能成为右区间最优解的 k+1。
                q.Push_Back(l);
            }
        }

        printf("%lld\n",f[n][1]);
    }

    return 0;
}

总结

个人感觉这道题的单队优化还是很难想的，能独立想出来的，单队也可以说是学的差不多了（蒟蒻个人见解勿喷）。