题解：CF1799D1 Hot Start Up (easy version)

· · 题解

三倍经验：P11233，CF1799D1，CF1799D2。

以下 b_i=cold_i,c_i=hot_i,m=k。

由于这是 CCF（Codeforces Copying Foundation）的题，所以先看数据范围：c_i\leq b_i，记住这条性质，这意味着能选 c_i 一定选 c_i。

这题一眼看上去，肯定是 dp，对于单组数据，考虑状态的设计：

设 dp_{i,x,y} 为枚举到 a_i 后，第一个 CPU 上一次运行的程序为 x，第二个 CPU 上一次运行的程序为 y 时，最小的花费。dp 数组初始值为极大值，dp_{0,x,y} 全是 0。

本题 n,m\leq 500,1\leq \sum n,\sum m \leq 500，而这个程序的时间复杂度是 O(tnm^2) 的，空间复杂度是 O(nm^2) 的，可以通过。

D0 空间复杂度是 O(nm^2) 的，直接炸飞，考虑优化空间。容易发现第一维 i 可以就地滚动，于是 dp_{x,y} 为枚举到 a_i 后，第一个 CPU 上一次运行的程序为 x，第二个 CPU 上一次运行的程序为 y 时，最小的花费，答案为 \min \{dp_{x,y}\}，这样空间复杂度就是 O(m^2) 的了。

每次转移只有 dp_{a_{i-1},y} 和 dp_{x,a_{i-1}} 有值，其它的地方都是极大值，且只转移到 dp_{x,a_i} 和 dp_{a_i,y}。考虑只转移这些值，其它的忽略掉，时间复杂度 O(nm)。

DP 转移式如下：

\begin{cases} dp_{x,a_i}=\min\{dp_{x,y}+b_{a_i},dp_{x,a_i}+c_{a_i}\}\\ dp_{a_i,y}=\min\{dp_{x,y}+b_{a_i},dp_{a_i,y}+c_{a_i}\} \end{cases}

本题 n,m\leq 5000,1\leq \sum n,\sum m \leq 5000，而这个程序的时间复杂度是 O(tnm) 的，空间复杂度是 O(m^2) 的，可以通过。

D1 空间复杂度是 O(m^2) 的，直接炸飞，考虑优化空间。我们之前说到：每次转移只有 dp_{a_{i-1},y} 和 dp_{x,a_{i-1}} 有值，其它的地方都是极大值，且只转移到 dp_{x,a_i} 和 dp_{a_i,y}。那能不能以这个为突破口，把其余地方的空间全都优化掉呢？

答案是可以的。显然有 dp_{x,y}=dp_{y,x}，我们可以将 dp 状态压缩成一维，优化掉 x 或 y（以下以 x 为例）令 dp_y 表示 dp_{a_i,y}，则转移变成如下：

\begin{cases} dp_{a_i,a_{i-1}}=\min\{dp_{a_{i-1},y}+b_{a_i},dp_{a_{i-1},a_i}+c_{a_i}\}\\ dp_{a_i,y}=dp_{a_{i-1},y}+b_{a_i} \end{cases}

再优化到：

\begin{cases} dp_{a_{i-1}}=\min\{dp_y+b_{a_i},dp_{a_i}+c_{a_i}\}\\ dp_{y}=dp_y+b_{a_i} \end{cases}

看完这个式子突然有一种很显然的的感觉（不然为什么 D1 D2 就差 200），感觉那些注意力惊人的大佬能一眼秒？

发现这个式子转移还是 O(m) 的，怎么办？

注意到第二个式子在就地滚动，可以直接省略，用一个变量 ans 来记录第二个式子的 dp_y 加了多少，则有：

\begin{cases} ans=ans+c_{a_i} & a_i=a_{i-1}\\ ans=ans+b_{a_i} & a_i\neq a_{i-1} \end{cases}

此时式子只剩：

dp_{a_{i-1}}=\min\{dp_y+b_{a_i},dp_{a_i}+c_{a_i}\}-c_{a_i}

转移还是 O(m)？

对于 dp_y，我们记一个 minn=\min\{dp_{a_{i-1}}\}，式子变为：

dp_{a_{i-1}}=\min\{minn+b_{a_i},dp_{a_i}+c_{a_i}\}-c_{a_i}

转移 O(1)，总共时间复杂度 O(tn)，空间复杂度 O(n+m) 可以通过。

代码（only D2）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+1;
int t,n,m,a[N],b[N],c[N],dp[N],minn,ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    memset(dp,0x3f,sizeof dp);
    while(t--){
        minn=0;
        ans=0;
        for(int i=1;i<=n;i++) dp[a[i]]=0x3f3f3f3f;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>b[i];
        for(int i=1;i<=m;i++) cin>>c[i];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            if(a[i]==a[i-1]) ans+=c[a[i]];
            else{
                ans+=b[a[i]];
                dp[a[i-1]]=min(dp[a[i]]+c[a[i]],minn+b[a[i]])-b[a[i]];
                minn=min(minn,dp[a[i-1]]);
            }
        }
        cout<<minn+ans<<'\n';
    }
}