Độ khó tối thiểu của lịch công việc trong C++

Muốn lập lịch danh sách công việc trong d ngày. Công việc phụ thuộc: để làm việc i phải hoàn thành tất cả j < i. Phải làm ít nhất 1 việc mỗi ngày. Độ khó lịch = tổng độ khó từng ngày. Độ khó ngày = max độ khó việc làm trong ngày đó. Cho mảng taskDifficulty và số d, tìm độ khó tối thiểu. Trả về -1 nếu không thể.

Ví dụ: taskDifficulty = [6,5,4,3,2,1], d = 2. Ngày 1: 5 việc đầu (max=6), ngày 2: việc cuối (max=1). Tổng = 7.

Giải pháp

Quy hoạch động đệ quy với memoization:

• solve(v, idx, k, dp): độ khó tối thiểu từ idx với k ngày còn lại
• Cơ sở: idx==n và k==0 → 0; k<0 hoặc idx==n và k>0 → INF
• Duyệt i từ idx đến n-1: maxVal = max(maxVal, v[i]), ret = min(ret, maxVal + solve(v, i+1, k-1, dp))
• Lưu dp[idx][k] = ret
• Main: nếu d > n trả về -1, ngược lại khởi tạo dp[n][d+1] = -1, gọi solve(j, 0, d, dp)

Ví dụ mã C++

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int solve(vector<int>& v, int idx, int k, vector<vector<int> >& dp) { 
        if (idx == v.size() && k == 0) return 0; 
        if (k < 0 || (idx == v.size() && k > 0)) return 1e6; 
        if (dp[idx][k] != -1) return dp[idx][k]; 
        
        int maxVal = 0; 
        int ret = INT_MAX; 
        for (int i = idx; i < v.size(); i++) { 
            maxVal = max(v[i], maxVal); 
            ret = min(ret, maxVal + solve(v, i + 1, k - 1, dp)); 
        } 
        return dp[idx][k] = ret; 
    } 
    
    int minDifficulty(vector<int>& j, int d) { 
        int n = j.size(); 
        if (d > n) return -1; 
        vector<vector<int> > dp(n, vector<int>(d + 1, -1)); 
        return solve(j, 0, d, dp); 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {6,5,4,3,2,1}; 
    cout << (ob.minDifficulty(v, 2)); 
    return 0; 
}

Đầu vào

{6,5,4,3,2,1}, 2

Đầu ra

7