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

· · 题解

首先有个 n^3 的暴力。假设 dp_{l,r} 为确定答案在区间 [l,r] 后需要的最小代价，那么可以得到式子：

dp_{i,j}=\min_{i<k<j}\max\{dp_{i,k},dp_{k+1,j}\}+a_k

枚举区间长度，或者倒序枚举 i 都可以在 n^3 的时间复杂度完成。

考虑优化，爆推式子好像有点难，那么观察式子，里面有一个 \max 和一个 \min，考虑先拆开里面的 \max，也就是对于每一个 (i,j) 对子，找到一个最小的 k=f(i,j) 满足 dp_{i,k}>dp_{k+1,j}。二分查找可以做到 O(n^2\log n)，但是认真观察可以发现 f(i,j+1) \ge f(i,j)，并且判断是否成立是 O(1) 的，所以决策单调性优化到了 O(n^2)。

想到这里，接下来的部分就顺理成章了，分类讨论中转点 k 和 f(i,j) 的关系：

（1）k < f(i,j)，那么是一个形如 dp_{k,j}+a_k 的式子的值，这个和 i 无关，所以对于 j 维护一个单调队列即可。这里可能浪费一倍空间，解决方法有两个，第一个是单调队列和 dp 用一个数组，另外一个是先枚举 j，再倒序枚举 i。（这样空间还能用 vector 优化到 \dfrac{1}{2}n^2 个数）

（2）k \ge f(i,j)，那么是形如 dp_{i,k}+a_k 的东西，显然这个关于 k 单调递增，直接输出 k=f(i,j) 时的答案即可。

代码不长，即使手写单调队列优化常数都只有 30 行。关于常数方面，区间 dp 中由于倒序枚举的特殊性，所有 dp[l][r] 写成 dp[r][l] 能快 3 倍，但是不优化也能过。

代码还是放下，主要是 @xiaoyaowudi 写的。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rl register long long
#define N 7010
ll a[N],f[N][N],n,t;
struct my_deque{
    ll dat[N];int l,r;
    inline void clear(){l=r=0;}
    inline void push_back(rl a){dat[r++]=a;}
    inline void pop_back(){--r;}
    inline void pop_front(){++l;}
    inline bool empty(){return l==r;}
    inline int front(){return dat[l];}
    inline int back(){return dat[r-1];}
}qe;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(rl i=1;i<=n;++i)
            scanf("%lld",&a[i]);
        for(int j=2;j<=n;++j){
            qe.clear();
            qe.push_back(j-1);
            f[j][j-1]=a[j-1];
            for(int i=j-2,l=j;i;--i){
                while(f[l-1][i]>f[j][l] && l>i) --l;
                while(!qe.empty() && l<=qe.front()) qe.pop_front();
                f[j][i]=a[l]+f[l][i];
                if(!qe.empty()) f[j][i]=min(f[j][i],f[j][qe.front()+1]+a[qe.front()]);
                while(!qe.empty() && a[qe.back()]+f[j][qe.back()+1]>=a[i]+f[j][i+1]) qe.pop_back();
                qe.push_back(i);
            }
        }
        printf("%lld\n", f[n][1]);
    }
    return 0;
}

关于乱搞：

值得一提的是，如果令 f(i,j) 为区间 [i,j] 的决策点，这个在 i 固定的时候并没有决策单调性。最简单的反例是

n=7,a_i=i

并且，dp 的转移式不是单峰的，三分也不能解决。不知道有没有带一个 \log 的做法。（不容易直接优化到 n^2 的）