CF1799D1 Hot Start Up (easy version) 题解

· · 题解

没有多难（老师说这题蓝得发绿），直接 DP。

首先设 dp_{i,j} 表示第 i 个程序执行完后，两个 CPU 运行的最后一个程序一个编号为 i（也就是第 i 个程序）、另一个类型为 j，最短运行完前 i 个程序的时间。那么显然有 answer=\min\{dp_{n,i}\}。

稍微思考可得转移方程（箭头左边的数与箭头右的求最小值并更新箭头左的数）：\ 若 dp_{i,j} 是合法状态，且 i<n，则

dp_{i+1,j}\larr\begin{cases} dp_{i,j}+hot_{a_{i+1}},a_i=a_{i+1}\\ dp_{i,j}+cold_{a_{i+1}},a_i\ne a_{i+1} \end{cases}\\ dp_{i+1,a_i}\larr\begin{cases} dp_{i,j}+hot_{a_{i+1}},j=a_{i+1}\\ dp_{i,j}+cold_{a_{i+1}},j\ne a_{i+1} \end{cases}

转移的次序和我以前学的不一样，是枚举合法状态推出后继状态。边界：在 dp 中 dp_{0,0}=0，其它的都是 \infty。也就是说 \infty 表示不知道这个位置是否合法，然后通过合法状态推出的数一定合法所以替代掉 \infty。

时间复杂度 O(nk)，n,k\le5000，不会爆。

AC Code

#include <iostream>
#define int long long
#define inf 1000000000000000000ll
using namespace std;
int n,k,a[5001],h[5001],c[5001],dp[5001][5001];
void solve() {
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=k;i++)
        cin>>c[i];
    for(int i=1;i<=k;i++)
        cin>>h[i];
    for(int i=0;i<=n;i++)
        fill(dp[i],dp[i]+k+1,inf);
    dp[0][0]=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<=k;j++) if(dp[i][j]<inf) {
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+(a[i+1]==a[i]?h[a[i+1]]:c[a[i+1]]));
            dp[i+1][a[i]]=min(dp[i+1][a[i]],dp[i][j]+(a[i+1]==j?h[a[i+1]]:c[a[i+1]]));
        }
    int ans=inf;
    for(int i=0;i<=k;i++)
        ans=min(ans,dp[n][i]);
    cout<<ans<<'\n';
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false),
    cout.tie(nullptr);
    signed t;
    for(cin>>t;t--;solve());
    return 0;
}

如果觉得这题简单可以试试这题的升级版，我们老师说这个蓝的发紫~~~