C3-Zexal的多路流水线调度

 

题目描述

Zexal的偶像SkyLee想要组装一台电脑，而电脑需要按照固定的顺序进行安装，不能把配件都买好一起安装（因为SkyLee只会按照顺序安装，他分不清内存条和显卡）。

城市里有n个电脑城，并且每个电脑城都有所有的配件卖，除了价格不同外完全一样。一台电脑一共有m个配件，按照安装顺序编号为1−m。

假设第i个电脑城的编号为j的配件售价为p[i][j]，从第i个电脑城到第j个电脑城的交通费用为f[i][j]。

那么SkyLee组装好整台电脑最少需要多少钱呢？（配件费用+交通费用）

输入

多组数据输入

第一行两个整数n和m，分别为电脑城数量和配件数量（2<n,m≤500）

接下来n行，每行m个整数，表示配件的价格p[i][j]（0≤p[i][j]≤500）

接下来n行，每行n个整数，表示交通费用f[i][j]（0≤f[i][j]≤500）

输出

对于每组数据，输出一行，为最小费用

输入样例

3 3
10 1 10
8 5 10
10 10 2
0 5 2
1 0 5
1 1 0

输出样例

14

分析

将两条流水线的ALS扩展为多条流水线，基本思路不变，只是每个工序都需要将每一条流水线可能的情况枚举。

第i个电脑城的编号为j的配件售价为p[i][j]

从第k个电脑城到第i个电脑城交通费用f[k][i]

从第k个电脑城到第i个电脑城买第j个配件dp[i][j]

转移方程dp[i][j] = min(dp[i][j], dp[k][j-1] + f[k][i]);

代码

#include <iostream>
#include <iomanip>
#include <cstring>
#define N 506
using namespace std;
int p[N][N], f[N][N], dp[N][N];



int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        memset(dp,999999,sizeof(dp));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
                cin>>p[i][j];
            dp[i][0] = p[i][0];
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin>>f[i][j];
        for(int j = 1; j < m; j++)
            for(int i = 0; i < n; i++)
            {
                for(int k = 0; k < n; k++)
                {
                    dp[i][j] = min(dp[i][j], dp[k][j-1] + f[k][i]);
                }
                dp[i][j] += p[i][j];
            }
        int ans = 0x3f3f3f;
        for(int i = 0; i < n; i++)
            ans = min(ans, dp[i][m-1]);
        cout<< ans << endl;
    }

    return 0;
}