Hot Start Up (easy version)

Created by LXC on Fri May 19 19:14:39 2023

https://codeforces.com/problemset/problem/1799/D1

ranting: 1900

tag: dp

题意

现在由k种程序

在一个cpu中如果执行了第$i$种和然后又执行第$i$种程序，则花费$hot_i$时间。否则是$cold_i$时间

现在有一个长度为n的需要执行的程序序列。有两个cpu，两个cpu只能同时运行一个。

运行完所有程序所需要的时间是多少。

题解

考虑每个程序放置的是哪个cpu，总共有$2^n$种状态，可以考虑关于前缀的子问题。

但是当前的程序放那个cpu，如果cpu跑的程序和当前一样则用的是hot时间，否则是cold时间。
所以需要知道每个cpu之前跑的是什么程序，但是两个cpu，共有$O(k^2)$种。再加上当前放置的程序共有$O(nk^2)$种状态。

但是其实不需要记录两个cpu的最近状态，当我们放置第i个程序的时候，第i-1个程序必定在两个cpu中。

所以我们可以这样设状态：

$f_{i,j}$ 在第i个程序放在第一个cpu，且第二个cpu的最近跑的程序是j的情况下，前i个程序的最少运行时间。

$g_{i,j}$ 在第i个程序放在第二个cpu，且第一个cpu的最近跑的程序是j的情况下，前i个程序的最少运行时间。

状态转移

$f_{i,j} = \left \lbrace \begin{array}{ll}\max \limits_{j=0}^{k}f_{i-1,j} + hot_{a_i} & a_i = a_{i-1} \\ \max \limits_{j=0}^{k}f_{i-1,j} + cold_{a_i} & a_i \ne a_{i-1} \end{array} \right .$

$f_{i,a_{i-1}} = \left \lbrace \begin{array}{ll}\max \limits_{j=0}^{k}g_{i-1,j} + hot_{a_i} & a_i = j \\ \max \limits_{j=0}^{k}g_{i-1,j} + cold_{a_i} & a_i \ne j \end{array} \right .$

$g_{i,j} = \left \lbrace \begin{array}{ll}\max \limits_{j=0}^{k}g_{i-1,j} + hot_{a_i} & a_i = a_{i-1} \\ \max \limits_{j=0}^{k}g_{i-1,j} + cold_{a_i} & a_i \ne a_{i-1} \end{array} \right .$

$g_{i,a_{i-1}} = \left \lbrace \begin{array}{ll}\max \limits_{j=0}^{k}f_{i-1,j} + hot_{a_i} & a_i = j \\ \max \limits_{j=0}^{k}f_{i-1,j} + cold_{a_i} & a_i \ne j \end{array} \right .$

初始化 $f_{1,0} = g_{1,0} = cold_{a_1}，otherwise\ f_{i,j} = \infty$

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 5005
#define MOD 998244353
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;

ll a[N], cold[N], hot[N];
ll f[N][N], g[N][N];

void sol() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= k; i++) {
        cin >> cold[i];
    }
    for (int i = 1; i <= k; i++) {
        cin >> hot[i];
    }
    // 每组数据都按照最坏的情况初始化 超时
    // memset(f, 0x3f, sizeof(f));
    // memset(g, 0x3f, sizeof(g));
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            g[i][j] = f[i][j] = INF;
        }
    }
    g[1][0] = f[1][0] = cold[a[1]];
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            f[i][j] =
                min(f[i][j],
                    f[i - 1][j] + (a[i] == a[i - 1] ? hot[a[i]] : cold[a[i]]));
            f[i][a[i - 1]] =
                min(f[i][a[i - 1]],
                    g[i - 1][j] + (a[i] == j ? hot[a[i]] : cold[a[i]]));
            g[i][j] =
                min(g[i][j],
                    g[i - 1][j] + (a[i] == a[i - 1] ? hot[a[i]] : cold[a[i]]));
            g[i][a[i - 1]] =
                min(g[i][a[i - 1]],
                    f[i - 1][j] + (a[i] == j ? hot[a[i]] : cold[a[i]]));
        }
    }
    ll mn = g[0][0];
    for (int i = 0; i <= k; i++) {
        mn = min({mn, f[n][i], g[n][i]});
    }
    cout << mn << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}