题解：CF1799D1 Hot Start Up (easy version)

TTpandaS · 2024-10-27 08:58:20 · 题解

首先如果一个机器贡献是 hot，那么一定是与上一个和它类型相同的匹配，所以转移只需要考虑 lst_{a_i} 即可。现在需要算出 [lst_{a_i}+1,i] 全部为另一种颜色的贡献，发现 [lst_{a_i}+2,i] 是好算的，lst_{a_i}+1 的贡献是不知道的，但是此时 lst_{a_i} 和 lst_{a_i}+1 颜色是确定的，所以用 lst_{a_i}+1 的 DP 值转移即可，DP 只需要记录这一位和上一位的颜色即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int T;
int n,k,a[N],cold[N],hot[N];
int sum[N],dp[N][2][2],lst[N];
void solve(){
    scanf("%lld %lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        lst[a[i]]=0;
    }
    for(int i=1;i<=k;i++){
        scanf("%lld",&cold[i]);
    }
    for(int i=1;i<=k;i++){
        scanf("%lld",&hot[i]);
    }   
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1];
        if(a[i]==a[i-1]){
            sum[i]+=hot[a[i]];
        }
        else{
            sum[i]+=cold[a[i]];
        }
    }
    if(n==1){
        printf("%lld\n",cold[a[1]]);
        return;
    }
    dp[2][1][0]=dp[2][0][1]=cold[a[1]]+cold[a[2]];
    if(a[1]==a[2]){
        dp[2][1][1]=dp[2][0][0]=cold[a[1]]+hot[a[2]];
    }
    else{
        dp[2][1][1]=dp[2][0][0]=cold[a[1]]+cold[a[2]];
    }
    lst[a[1]]=1;
    lst[a[2]]=2;
    for(int i=3;i<=n;i++){
        dp[i][0][0]=min(dp[i-1][0][0],dp[i-1][0][1])+cold[a[i]];
        dp[i][1][0]=min(dp[i-1][0][0],dp[i-1][0][1])+cold[a[i]];
        dp[i][0][1]=min(dp[i-1][1][0],dp[i-1][1][1])+cold[a[i]];
        dp[i][1][1]=min(dp[i-1][1][0],dp[i-1][1][1])+cold[a[i]];
        if(lst[a[i]]!=0){
            if(lst[a[i]]==i-1){
                dp[i][1][1]=min(dp[i][1][1],min(dp[i-1][1][0],dp[i-1][1][1])+hot[a[i]]);
                dp[i][0][0]=min(dp[i][0][0],min(dp[i-1][0][0],dp[i-1][0][1])+hot[a[i]]);
            }
            else{
                dp[i][0][1]=min(dp[i][0][1],dp[lst[a[i]]+1][1][0]+(sum[i-1]-sum[lst[a[i]]+1])+hot[a[i]]);
                dp[i][1][0]=min(dp[i][1][0],dp[lst[a[i]]+1][0][1]+(sum[i-1]-sum[lst[a[i]]+1])+hot[a[i]]);
            }
        }
        lst[a[i]]=i;
    }
    printf("%lld\n",min(min(dp[n][0][0],dp[n][0][1]),min(dp[n][1][0],dp[n][1][1])));
}
signed main(){
    scanf("%lld",&T);
    while(T--){
        solve();
    } 
    return 0;
}