Перейти к содержанию

Реализации алгоритмов/Задача о расписании работы конвейера

Материал из Викиучебника — открытых книг для открытого мира

Реализация классической задачи о расписании работы конвейера на разных языках программирования.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int S_1, S_2; // время постановки на конвеер
int N; // всего станков
vector<int> a; // время выполнения на станках первого конвеера
vector<int> b; // время выполнения на станках второго конвеера
vector<int> tb; // время перестановки на c первого конвеера на второй
vector<int> ta; // время перестановки на c второго конвеера на первый
vector<vector<int>> dp(2); //дп
int answer; //ответ

int main() {
    cin>>S_1>>S_2;
    cin>>N;
    a.resize(N);
    for(int i = 0; i < N; i++) cin>>a[i];
    b.resize(N);
    for(int i = 0; i < N; i++) cin>>b[i];
    tb.resize(N);
    for(int i = 0; i < N - 1; i++) cin>>tb[i];
    ta.resize(N);
    for(int i = 0; i < N - 1; i++) cin>>ta[i];
    dp[0].push_back(S_1 + a[0]);
    dp[1].push_back(S_2 + b[0]);
    for(int i = 1; i < N; i++) {
        dp[0].push_back(min(dp[0].back(), dp[1].back() + ta[i-1]) + a[i]);
        dp[1].push_back(min(dp[1].back(), dp[0].back() + tb[i-1]) + b[i]);
    }
    answer = min(dp[0].back() + S_1, dp[1].back() + S_2);
    cout<<"\n"<<answer<<"\n";
    return 0;
}