CF1799D2 Hot Start Up (hard version) 题解

· · 题解

CSP-S 2024 原题居然还能交题解？

解题思路

定义 f_{i,j} 为运行了前 i 个程序，另一个（与第 i 个程序运行所在 CPU 不同） CPU 运行到的最后一个程序种类为 j 的最短时长。

对于当前程序，我们有两种运行方法：接着上一个程序所在的 CPU 继续运行、换一个 CPU 运行。当前程序冷热启动情况，结合状态设计是显然的。

所以有转移方程如下：

f_{i,j}=\min\begin{cases}f_{i-1,j}+hot_{a_i}&a_i=a_{i-1}\\f_{i-1,j}+cold_{a_i}&a_i\neq a_{i-1}\end{cases} f_{i,a_{i-1}}=\min\begin{cases}f_{i-1,a_{i}}+hot_{a_{i}}\\f_{i-1,j}+cold_{a_i}&j\neq a_i\\f_{i,a_{i-1}}\end{cases}

时间复杂度为 O(nk)，需要优化。

我们不妨搞一个滚动数组，压掉 i 这一维。

f_{j}=\min\begin{cases}f_{j}+hot_{a_i}&a_i=a_{i-1}\\f_{j}+cold_{a_i}&a_i\neq a_{i-1}\end{cases} f_{a_{i-1}}=\min\begin{cases}f_{a_{i-1}}+hot_{a_{i}}\\f_{j}+cold_{a_i}&j\neq a_i\\f_{a_{i-1}}\end{cases}

可以显然地观察到，转移可以表示为数组 f 的一些整体相加（和上一个程序的 CPU 相同），和一些个别的单点取 \min（换了一个 CPU）。

打一个线段树去维护可以做到 O(n\log{k})。

事实上还可以做到更优。

我们考虑维护一个 f 的全局懒标记 laz，一个当前的 f 全局最小值 minn。

对于整体转移，继承 CPU运行，直接给 laz 加上一个值。

对于单点取 \min，就让 f_{a_{i-1}} 和撤销全局操作后，加上更换 CPU 运行的时间取 min，并更新 minn 即可。 ::::info[为什么我们忽略了更换 CPU 运行时的整体操作] 注意到 hot_i\leq cold_i 且转移来源相同，若继承 CPU 热启动，显然优于更换 CPU 的冷启动；若继承 CPU 冷启动，与更换 CPU 冷启动等价。该约束条件也是上述暴力转移方程写法成立的原因。 ::::

时间复杂度 O(n)。

参考代码

#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+10;
int a[N],v1[N],v2[N],f[N];
int t,n,k,ans,laz,minn;
void read(int &x) {
    x=0;int f=1;
    char s=getchar();
    for(;s<'0'||s>'9';s=getchar()) f=s=='-'?-f:f;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    x*=f;
}
signed main(){
    ios::sync_with_stdio(false);
    read(t);
    while(t--){
        read(n),read(k);
        for(int i=1;i<=n;i++){
            read(a[i]);
        }
        for(int i=1;i<=k;i++){
            read(v1[i]);
        }
        for(int i=1;i<=k;i++){
            read(v2[i]);
        }
        for(int i=1;i<=k;i++){
            f[i]=INF;
        }
        laz=minn=0;
        for(int i=1;i<=n;i++){
            if(a[i]==a[i-1]){
                laz+=v2[a[i]];
                f[a[i-1]]=min(f[a[i]],minn-v2[a[i]]+v1[a[i]]);
            }else{
                laz+=v1[a[i]];
                f[a[i-1]]=min(f[a[i]]-v1[a[i]]+v2[a[i]],minn);
            } 
            minn=min(minn,f[a[i-1]]);
        }
        cout<<minn+laz<<'\n';
    }
    return 0;
}

AC record

Written by toolong114514 on 2025.8.16.