CF1799D1题解

· · 题解

题目大意

有2个处理器，n个程序，共k个种类，要求我们用这2个处理器处理程序，求处理全部程序所需最短时间。

这道题，用dp可以比较简单、轻松地解决。

dp数组分析

我们定一个2维数组，f[i][j]，i代表已经运行了第i个程序，j表示不运行第i个程序的那个处理器运行的程序类型。

状态转移方程分析

根据题意，我们可以得到一个信息，要么是处理了第i个程序的处理器处理第i+1个程序，要么是另一个处理器处理第i+1个程序。

因此我们可以得出4个转移方程：

  2. f[i+1][a[i]]=min(f[i][j]+cold[a[i+1]])$或者 $f[i+1][a[i]]=min(f[i][j]+hot[a[i+1]])$$($另一个处理器运行了第$i+1$个程序$）

    答案分析

    状态转移后，因为有一个处理器会处理第n个程序，另一个处理器会不处理或者处理第1~k种类型的程序。所以答案是f[n][1]~f[n][k]中的最小值。

接下来，上代码

#include <bits/stdc++.h>
#define int long long
#define INF 1e9
using namespace std;

const int maxn=5005;

int f[maxn][maxn],cold[maxn],hot[maxn],n,k,t,a[maxn];

signed main() {
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                f[i][j]=0x3f3f3f3f3f3f3f3f;//设极限值，不要用1e9，会被数据卡掉
            }
        }
        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];
        f[1][0]=cold[a[1]];
        for(int i=1;i<n;i++){
            for(int j=0;j<=k;j++){//j=0表示另一个处理器没有处理任何程序
                if(a[i+1]==a[i]) f[i+1][j]=min(f[i+1][j],f[i][j]+hot[a[i+1]]);
                else f[i+1][j]=min(f[i+1][j],f[i][j]+cold[a[i+1]]);
                //状态转移方程1，类型相同运行时间为hot[a[i+1]],否则为cold[a[i+1]]
                if(a[i+1]==j) f[i+1][a[i]]=min(f[i+1][a[i]],f[i][j]+hot[a[i+1]]);
                else f[i+1][a[i]]=min(f[i+1][a[i]],f[i][j]+cold[a[i+1]]);
                //状态转移方程2，类型相同运行时间为hot[a[i+1]],否则为cold[a[i+1]]
            }
        }
        int ans=0x3f3f3f3f3f3f3f3f;//同理，设极限值，1e9不用，防止被卡
        for(int i=0;i<=k;i++){
            ans=min(ans,f[n][i]);//答案取最小值
        }
        cout<<ans<<endl;
    }
    return 0;
}