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

· · 题解

2022.07.05 改了一个 typo。

突然发现有这题，推荐一做。

和出题者谈话后觉得我应该要提前4年退役了。

暴力就不说了。

\texttt{Subtask 2 }

如果数在一个区间 [l,r]，我们随便选一个数 k，会得到这个数是否大于 k，并且付出 a_k 的代价。复出后，我们可以得到信息：电线的长度 x\in [l,k] 或者 x\in [k+1,r]。这不就是区间dp吗qwq，

设计状态 f(l,r) 代表知道 x\in [l,r] 后要多少步确定 x。转移方程为 f(l,r)=\min\limits_{l\le k<r} \small \max (f(l,k),f(k+1,r))+a_k

复杂度 O(Tn^3)。

namespace subtask2 {
    int f[509][509];
    void main(){
        memset(f,0x3f,sizeof(f));
        per(l,n,1) rep(r,l,n) {
            if(l==r) f[l][r]=0;
            else if(r-l==1) f[l][r]=a[l];
            else rep(k,l,r-1) f[l][r]=min(f[l][r],max(f[l][k],f[k+1][r])+a[k]);
        }
        printf("%lld\n",f[1][n]);
    }
}

\texttt{Subtask 2 }

这个决策 k 很烦人。

把决策和答案打印出来，发现…… （大样例的样例2的第三个数据 l=7 的情况，打印每一行为 l,r,决策,f[l][r]）

...
7 9 8 15
7 10 8 17
7 11 9 24
7 12 10 27
7 13 9 32
7 14 10 35
7 15 11 38
...

决策没有特别规律。

再看看式子，\min\limits_{l\le k<r} \small \max (f(l,k),f(k+1,r))+a_k。好像类似于 f_x+a_x 的形式，有点单调队列的意思。

但是，这个 \max 直接埋没了这个式子优化的潜力。所以我们直接分类讨论，看 f(l,k)>f(k+1,r) 的情况和 f(l,k)<f(k+1,r) 的情况。

稍微思考一下得知，由于上面打表（和思考）得知，f(l,k) 随着 k 的增加而增加，f(k+1,r) 随着 k 的增大而减小，所以 f(l,k)-f(k+1,r) 是单调的，所以我们只需要找到最小的 k 使得 f(l,k)>f(k+1,r)，即这个分界点。

现在有 3 步，找到分界点，讨论 f(l,k)>f(k+1,r) 的情况和讨论 f(l,k)<f(k+1,r) 的情况。

Step 1 找到分界点

这里有单调性！

对于 f(l,x) 分界点是单调不降的！也就是 f(l,r) 的分界点在 f(l,r+1) 的左边或者相同。（傻子都能想出来？）

Step 2 计算 f(l,k)>f(k+1,r) 的情况

这种情况，原式化为 f(l,r)=\min f(l,k)+a_k。这玩意儿是单调的，所以每次取最左端的 k 即可。

Step 3 计算 f(l,k)\le f(k+1,r) 的情况

这个少许麻烦了一些。原式化为 f(l,r)=\min f(k+1,r)+a_k。

按照最朴素的单调队列维护即可，不需要什么分类讨论。（如果单调队列不会写的，建议抛弃这道题去学习单调队列）。

namespace ac {
    int f[7009][7009],q[7009];
    void main() {
        rep(r,2,n) {
            int p=r;
            int ll=1,rr=2; q[1]=r;
            per(l,r,1) {
                if(l==r) {f[l][r]=0;continue;}
                else if(r-l==1) {f[l][r]=a[l];continue;}
                while(p>l&&f[p][r]<f[l][p-1]) p--;          //Step1
                f[l][r]=f[l][p]+a[p];                       //Step2
                while(ll<rr&&q[ll]>=p) ll++;                    //Step3 (and the next 3 lines)  
                if(ll<rr) f[l][r]=min(f[l][r],f[q[ll]+1][r]+a[q[ll]]);
                while(ll<rr&&f[q[rr-1]+1][r]+a[q[rr-1]]>=f[l+1][r]+a[l]) rr--;
                q[rr++]=l;
            }
        }
        printf("%lld\n",f[1][n]);
    }
}

尽管代码不长，但做的真的累。