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

Giả sử chúng ta muốn lên lịch cho một danh sách các công việc trong d ngày. Các nhiệm vụ phụ thuộc vì vậy, để làm việc trên nhiệm vụ thứ i, chúng ta phải hoàn thành tất cả các tác vụ j trong đó 0 <=j

Chúng ta phải hoàn thành ít nhất một nhiệm vụ mỗi ngày. Khó khăn của một lịch trình công việc thực sự là tổng các khó khăn của mỗi ngày trong số ngày d. Khó khăn của một ngày là độ khó tối đa của nhiệm vụ được thực hiện trong ngày đó.

Vì vậy, chúng ta có một mảng các số nguyên được gọi là taskDifficulty và một số nguyên d. Khó khăn của công việc thứ i là taskDifficulty [i]. Chúng ta phải tìm ra độ khó tối thiểu của một lịch trình công việc. Nếu chúng tôi không thể tìm thấy lịch trình cho các nhiệm vụ, hãy trả về -1.

Vì vậy, nếu đầu vào giống như taskDifficulty =[6,5,4,3,2,1], d =2,

thì đầu ra sẽ là 7, như ngày 1 chúng ta có thể hoàn thành 5 công việc đầu tiên, tổng độ khó là 6. Bây giờ vào ngày 2 chúng ta có thể hoàn thành công việc cuối cùng, tổng độ khó là 1, do đó độ khó của lịch trình sẽ là 6 + 1 =7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm giải quyết (), điều này sẽ lấy một mảng v, idx, k, một dp 2D,

• nếu idx bằng với kích thước của v và k bằng 0, thì -

  • trả về 0

• nếu k <0 hoặc idx giống với kích thước của v và k> 0, thì -

  • trả về 1 ^ 6

• nếu dp [idx, k] không bằng -1 thì -

  • trả về dp [idx, k]

• maxVal:=0

• ret:=inf

• để khởi tạo i:=idx, khi tôi

  • maxVal:=tối đa v [i] và maxVal

  • ret:=tối thiểu ret và maxVal + giải (v, i + 1, k - 1, dp)

• dp [idx, k]:=ret

• trả lại ret

• Từ phương thức chính, hãy làm như sau -

• n:=kích thước của j

• nếu d> n, thì -

  • trả về -1

• Xác định một mảng 2D dp có kích thước n x (d + 1) và điền vào giá trị này bằng -1

• trả về giải quyết (j, 0, d, dp)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
   }
};
main(){
   Solution ob;
   vector<int> v = {6,5,4,3,2,1};
   cout << (ob.minDifficulty(v, 2));
}

Đầu vào

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

Đầu ra

7