C3-A 流水线调度1

题目描述

在某一车间有 33 条流水线，每条流水线有 mm 个装配站，编号都为 1,2,⋯ ,m1, 2, \cdots, m，每条流水线同样编号的装配站都执行相同的功能。拼装一个成品要按顺序经过 mm 个装配站才能加工完成，经过第 ii 条流水线的第 jj 个装配站要花费 pi,jp_{i,j} 的时间，且进入第一个装配站时无需移动时间，从第 ii 条流水线移动到第 jj 条流水线要花费 ti,jt_{i,j} 的时间，请问制造一个成品最少时间是多少？

题目分析

对于第ii条流水线的第jj个站点，他可能由33条流水线的任意一条的第j−1j-1个站点得到。所以可以用dp[i][j]dp[i][j]表示经过第ii条流水线的第jj​个站点要花费的最少时间，可得到状态转移方程如下：

dp[i][j]=min(dp[1][j−1]+t[1][i],dp[2][j−1]+t[2][i],dp[3][j−1]+t[3][i])+p[i][j]dp[i][j]=min(dp[1][j-1]+t[1][i],dp[2][j-1]+t[2][i],dp[3][j-1]+t[3][i])+p[i][j]

结束状态为到达第mm个站点，即min(dp[1][m],dp[2][m],dp[3][m])min(dp[1][m],dp[2][m],dp[3][m])

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
long long p[4][10100];
long long t123[5][5];
long long dp[4][10100];
long long min2(long long a, long long b)
{
    if (a < b)
    {
        return a;
    }
    else
    {
        return b;
    }
}
long long min3(long long a, long long b, long long c)
{
    long long Min = min2(a, b);
    return min2(Min, c);
}
int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        int m;
        scanf("%d", &m);
        for (int j = 1; j <= m; j++)
        {
            scanf("%lld", &p[1][j]);
        }
        for (int j = 1; j <= m; j++)
        {
            scanf("%lld", &p[2][j]);
        }
        for (int j = 1; j <= m; j++)
        {
            scanf("%lld", &p[3][j]);
        }
        for (int j = 1; j <= 3; j++)
        {
            for (int k = 1; k <= 3; k++)
            {
                scanf("%lld", &t123[j][k]);
            }
        }
        dp[1][1] = p[1][1];
        dp[2][1] = p[2][1];
        dp[3][1] = p[3][1];
        for (int j = 2; j <= m; j++)
        {
            for (int k = 1; k <= 3; k++)
            {
                dp[k][j] = min3(dp[1][j - 1] + t123[1][k], dp[2][j - 1] + t123[2][k], dp[3][j - 1] + t123[3][k]) + p[k][j];
            }
        }
        printf("%lld\n", min3(dp[1][m], dp[2][m], dp[3][m]));
    }
    return 0;
}