P9744 消除序列 题解

HFanGDoDM · 2023-10-15 23:12:37 · 题解

前置知识

ST 表

题意简述

给定一个长度为 n 的序列 v。初始时，\forall i\in\{1,2,\dots,n\},v_i=1。可执行以下操作：

选定一个 i\in\{1,2,\dots,n\}。然后：

• 以 a_i 的代价，\forall j\in \{1,2,\dots,i\}，令 v_j\leftarrow0。

• 以 b_i 的代价，令 v_i\leftarrow0。

• 以 c_i 的代价，令 v_i\leftarrow1。

有 q 次询问，每次询问给定集合 P，求使得序列 v 满足

的 最小总代价。

每次询问相互独立。

数据范围

做法

这里令 a_0=0，则答案为

正确性证明

做法

令初始的所有 v_i=1。

对于每一个位置 i，分别枚举 以下情况：

• 使用 a_i 的代价，将 v_1,v_2,\dots,v_i 全部赋值为 0，并将 v_1,v_2,\dots,v_i 中应当在最终序列中为 1 的所有元素 v_j，使用对应的 c_j 代价将其赋值为 1。

• 使用 b_i 的代价，将 v_i\leftarrow0。

• 使用 c_i 的代价，将 v_i\leftarrow1。

• 不做任何操作。

并继续向下 搜索，直到所有位置的操作都确定完。当所有位置操作做完后，判断当前序列是否与应当的最终序列相同。若不相同，则不合题意；若相同，则更新答案。

这样即可得到最终的答案。

正确性证明

考虑序列的第 i 个位置。

若使用上述第一种操作中，用 a_i 代价将 v_1,v_2,\dots,v_i 全部赋值为 0，则只有使用上述的 \sum c_j 代价将前面应当赋值为 1 的元素全部赋值为 1，才能保证当前序列是符合题意的序列。若其中含有其他操作，由于可以只使用 \sum c_j 代价进行赋值为 1 的操作，因此这些 其他操作一定是不必要的。

故：使用 a_i 代价将 v_1,v_2,\dots,v_i 全部赋值为 0 和使用 \sum c_j 代价将应当赋值为 1 的元素全部赋值为 1，这两个操作是 捆绑的。

对于该位置，也可以做上述的第二、三、四种操作。除此之外，再无别的操作。

因此，我们考虑到了 所有可能符合题意的操作，并从中筛选出了 所有真正符合题意的操作，并取最小答案。所以，这一思路是正确的。

具体实现

使用 深度优先搜索（DFS）实现。

对于每个询问，记 DFS(now,cost) 表示搜索到了 now 位置，当前的所有操作代价总和为 cost。则枚举该位置的四种情况：

记 \Delta 表示该位置的一种操作产生的 cost 增加量。

• 第一种情况：\Delta=a_{now}+\displaystyle\sum_{i=1}^{now}[i\in P]c_i。

• 第二种情况：\Delta=b_{now}。

• 第三种情况：\Delta=c_{now}。

• 第四种情况：\Delta=0。

继续向下执行 DFS(now+1,cost+\Delta) 即可。注意在枚举对应情况时，需要对序列对应元素 及时赋值。为了便于 回溯，可以在函数内部再开一个数组，记录 赋值前序列的前 now 个元素。

当 now=n+1 时，首先判断当前序列是否与应当得到的最终序列相同。若不同，直接返回；否则，更新答案。

最后输出答案。

时空复杂度分析

时间复杂度：由于对每个位置需要枚举 4 种情况，每次枚举的复杂度为 O(n)，因此对每个询问，总复杂度为 O(n4^n)。

总时间复杂度 O(4^nqn)，可以通过 测试点 3\sim4。

空间复杂度：在 DFS 中，递归的最大层数为 O(n) 级别，且每层需要新开一个大小为 O(n) 的临时数组。

空间复杂度为 O(n^2)，可以通过 测试点 3\sim4。

参考核心代码

void DFS(int now,long long cost){
    if(now==n+1){//如果已经确定所有位置的操作
        for(int i=1;i<=n;i++)
            if(tmp[i]!=fnl[i])//判断当前序列是否符合题意，若不符合直接返回
                return;
        ans=min(ans,cost);//否则更新答案
        return;
    }
    long long delta=a[now];//cost增加量
    vector<int>tmp1(now+1);
    for(int i=1;i<=now;i++)
        tmp1[i]=tmp[i];//临时数组，记录赋值前序列
    for(int i=1;i<=now;i++)
        tmp[i]=0;
    for(int i=1;i<=m;i++){
        if(p[i]>now)
            break;
        delta+=c[p[i]];
        tmp[p[i]]=1;//第一种情况
    }
    DFS(now+1,cost+delta);//向下继续搜索
    for(int i=1;i<=now;i++)
        tmp[i]=tmp1[i];//回溯
    tmp[now]=0;
    delta=b[now];
    DFS(now+1,cost+delta);//第二种情况
    tmp[now]=tmp1[now];//回溯
    tmp[now]=1;
    delta=c[now];
    DFS(now+1,cost+delta);//第三种情况
    tmp[now]=tmp1[now];//回溯
    DFS(now+1,cost);//第四种情况
}
...
        fill(tmp+1,tmp+1+n,1);//初始v[i]=1
        fill(fnl+1,fnl+1+n,0);
        for(i=1;i<=m;i++)
            fnl[p[i]]=1;//设定最终序列
        ans=INF;
        DFS(1,0);
        printf("%lld\n",ans);//输出答案

期望得分

做法

令 a_0=0。当 m=1 时，对于每个询问，其答案为

测试点 7

做法

令 a_0=0。则对于每个询问，其答案为

正确性证明

根据 测试点 3\sim4 的推理，我们知道，将 v_1,v_2,\dots,v_i 全部赋值为 0 的操作，往往和将所有 j\in P,j\in\{1,2,\dots,i\} 的 v_j\leftarrow1 的操作是 捆绑的。

并且由于 c_i=0，因此我们 可以无视 赋值为 1 的代价，只需要考虑 a_i 和 b_i 即可。

根据 测试点 1\sim2 的推理，若分别使用一次 a_i,a_j，这样的 总代价一定是更大的。因此，a_i 最多只可能使用一次。确定 a_i 使用位置后，只需要在其后面使用 b_i 将对应位置 v_i\leftarrow0。同时，由于 m\geqslant1，为尽可能 最小化总代价，只对最终序列中所有 v_i=0 的位置 i 使用 b_i 的代价即可。这些位置的代价是 必须使用，不可替代 的，若在其他位置使用其他代价，则都是不必要的。

我们证明了在这些答案中一定能够取到所有合法总代价的 下界，因此该思路是正确的。

具体实现

对于每一次询问，处理一个 后缀和 数组：sum_i=\displaystyle\sum_{j=i}^n[i\not\in P]b_i。

然后，扫一遍序列，按照上式计算即可。

最后输出答案。

时间复杂度分析

对于每次询问，需要处理后缀和数组，复杂度 O(n)；扫一遍序列并计算，复杂度 O(n)。

总时间复杂度 O(qn)。根据该解法，可以通过 测试点 1\sim2,7。

参考核心代码

    for(i=1;i<=m;i++)
        fnl[p[i]]=1;//设定最终序列
    for(i=n;i>=1;i--)
        sumb1[i]=sumb1[i+1]+b[i]*(!fnl[i]);//求b的上述后缀和
    for(i=0;i<=n;i++)
        ans=min(ans,a[i]+sumb1[i+1]);//根据上式计算答案
    printf("%lld\n",ans);//输出答案

期望得分

测试点 8\sim11

做法

对于每个询问，设 dp_i 表示考虑将序列 [1,p_i] 变为合法序列的 最小总代价。则

对于每个询问，令 p_{m+1}=n+1，且计算 dp_{m+1} 时的上述式子 不包含第三项，则答案为 dp_{m+1}。

正确性证明

根据前面几个测试点的推理，我们注意到，将一段 区间全部赋值为 0 已成为 重要的子问题。由于 \forall i\in\{1,2,\dots,m-1\},p_i\lt p_{i+1}，因此我们在考虑到 p_i 时，\forall j\in\{p_{i-1}+1,p_{i-1}+2,\dots,p_i-1\}，都需要使得最终序列的 v_j=0，且 p_{i-1} 及前面的最小代价已知。

现考虑所有可能将该区间全部赋值为 0 的方案：

• 对于一个 j\in\{p_{i-1}+1,p_{i-1}+2,\dots,p_i-1\}，使用 a_j 的代价，将 v_1,v_2,\dots,v_j 全部赋值为 0。此后需要立即执行 \forall k\in\{1,2,\dots,j\},k\in P,v_k\leftarrow1 的操作（具体原因见 测试点 3\sim4），并将位置 j 到 p_i-1 这段后缀中每个位置 k，全部用 b_k 的代价赋值为 0。a_j 不可能在不同位置使用多次，原因见 测试点 1\sim2,5\sim6 等，这里不再赘述。

• 对于该区间的所有位置 i，使用 b_i 代价，将 v_i\leftarrow0。由于该操作 基于 p_{i-1} 及前面已经操作好的序列，因此需要将该代价与 dp_{i-1} 累加。

• 在 p_i 位置使用 a_{p_i} 代价，将 v_1,v_2,\dots,v_{p_i} 全部赋值为 0，再 \forall k\in\{1,2,\dots,p_i\},k\in P,v_k\leftarrow1。该操作其实与第一个操作类似，但赋值为 1 的元素多了一个 v_{p_i}。

若 b_i 代价使用的下标不构成 \{1,2,\dots,p_i-1\} 的一段后缀，则该方案 一定不优，具体已在 测试点 1\sim2,5\sim6 中证明。

由于已知最终序列中 v_{p_i}=1，因此若使用 b_{p_i} 代价，单独将 v_{p_i}\leftarrow0，则该操作必然是 多余的。

综上，我们已经考虑到了此时所有可能的最优情况。

对于 dp_{m+1}，由于实际上不存在 n+1 位置的元素，因此只能将 v_{p_m},v_{p_m+1},\dots,v_n 全部赋值为 0，故其计算式中只有前两项。

因此，我们考虑完了 整个序列 的所有可能最优情况，故该思路是正确的。

具体实现

预处理 b 的前缀和 sumb。

对于每次询问，在枚举每个 p_i 时，先扫 p_{i-1}+2 到 p_i，计算前两项更新 dp 值，再 动态更新 \displaystyle\sum_{j=1}^{p_i}[j\in P]c_j。具体地，在每次计算完式中前两项后，直接将 c_{p_i} 加入该询问的 sumc。然后，计算第三项，更新 dp 值。

扫完每个 p_i 后，输出 dp_{m+1}。注意 dp_{m+1} 的计算中 没有第三项。

时间复杂度分析

预处理 sumb，复杂度为 O(n)。处理每次询问，扫的范围 刚好覆盖了整个序列，因此复杂度为 O(n)。扫 p_i 以及动态更新 sumc，复杂度 O(m)。

总时间复杂度 O(qn)。根据该解法，可以通过 测试点 3\sim11。

参考核心代码

    p[m+1]=n+1;//边界条件
    long long sumc=0;//每次询问动态更新在P中i的c[i]总和
    for(i=1;i<=m+1;i++){
        dp[i]=INF;
        for(j=p[i-1]+1;j<=p[i]-1;j++)
            dp[i]=min(dp[i],sumc+a[j]+sumb[p[i]-1]-sumb[j]);//式子中的第一项
        dp[i]=min(dp[i],sumb[p[i]-1]-sumb[p[i-1]]+dp[i-1]);//第二项
        sumc+=c[p[i]];//更新sumc
        if(i<=m)
            dp[i]=min(dp[i],a[p[i]]+sumc);//第三项，注意多了c[p[i]]
    }
    printf("%lld\n",dp[m+1]);//输出答案

期望得分

做法

记 val_i=a_i-\displaystyle\sum_{j=1}^ib_j，则前述有关 dp 表达式也可写作：

对于第一个式子，使用 分块 事先计算每个整块内的 val_i 的最小值即可。

正确性证明

上式中，第二、三个式子可以直接转移。

考虑将第一个式子进行变形：

可以发现，该式子变成了两个可预处理或动态更新的 定值 与一个 区间最小值 的形式，并且该序列 val 不会发生改变。因此我们可以直接运用分块思想，处理出每一块的最小值，加速询问的回答。

在恒等变形中每一步都保证正确，因此思路正确。

具体实现

预处理 val_i=a_i-sumb_i，并对 val 数组分块：每 O(\sqrt n) 个元素切成一个块，并预处理第 i 块中的 val_i 最小值 minn_i。其余预处理与 测试点 8\sim11 中所述相同。

对于每个询问，加速 dp 转移：对于第一个式子，计算 \displaystyle\min_{i=l}^rval_i 时，将询问区间划分为中间的 整块 与两端 散块。对于所有整块，直接取对应块中的最小值；否则，暴力扫对应 散块区间，求最小值。求出区间最小值，并计算，更新答案。

其余仍按照 dp 表达式转移即可。

最后输出 dp_{m+1}。

时间复杂度分析

由 测试点 8\sim11 的分析可知，复杂度瓶颈在 dp。对于每次转移，分块求区间最小值，整块最多 O(\sqrt n) 个，散块大小在 O(\sqrt n) 级别，复杂度为 O(\sqrt n)，因此回答每次询问的复杂度为 O(m\sqrt n)。

总时间复杂度 O((q+\sum m)\sqrt n)。根据该解法，可以通过 测试点 1\sim13。

参考核心代码

void InitBlock(){//初始化分块，预处理每个块val[i]最小值
    siz=sqrt(n);
    int num=n/siz+(n%siz!=0);
    for(int i=1;i<=n;i++)
        bel[i]=i/siz+(i%siz!=0);
    for(int i=1;i<=num;i++){
        int bl=siz*(i-1)+1,br=siz*i;
        minn[i]=INF;
        for(int j=bl;j<=br;j++)
            minn[i]=min(minn[i],val[j]);//预处理出最小值
    }
}
long long Min(int l,int r){//暴力求区间最小值
    long long ans=INF;
    for(int i=l;i<=r;i++)
        ans=min(ans,val[i]);
    return ans;
}
long long MinInterval(int l,int r){//求区间最小值
    if(l>r)
        return INF;
    if(bel[l]==bel[r])
        return Min(l,r);//同一块内直接暴力求
    long long ans=INF;
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
        ans=min(ans,minn[i]);//中间整块
    int rtl=bel[l]*siz,ltr=(bel[r]-1)*siz+1;
    return min({Min(l,rtl),ans,Min(ltr,r)});//两端散块取最小值，再与ans取min
}

期望得分

测试点 14\sim20

做法