N Servers

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.1 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int MinCost(int n, vector<int> &A, vector<int> &B) {
    vector<int> dp(n + 1, 0);  // dp[i] stores the minimum cost to use the first i servers
    dp[0] = 0, dp[1] = A[0] // Base case
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i-1] + A[i];  // Use the i-th server as a microservice
        if (i > 1) {
            dp[i] = min(dp[i], dp[i-2] + B[i-1] + B[i]);  // Use the i-th and (i-1)-th servers as a monolith
        }
        if (i > 2) {
            dp[i] = min(dp[i], dp[i-3] + B[i-2] + B[i-1] + B[i]);  // Use the i-th, (i-1)-th, and (i-2)-th servers as a monolith
        }
    }
    return dp[n-1];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> A(n), B(n);
        for (int i = 0; i < n; i++) {
            cin >> A[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> B[i];
        }
        cout << MinCost(n, A, B) << endl;
    }
    return 0;
}