C++에서 작업 일정의 최소 난이도

d일에 작업 목록을 예약하려고 한다고 가정합니다. 작업은 종속적이므로 i 번째 작업을 수행하려면 0 <=j 인 모든 작업 j를 완료해야 합니다.

우리는 매일 적어도 하나의 작업을 완료해야 합니다. 작업 일정의 난이도는 실제로 d일 중 각 요일의 난이도를 합한 것입니다. 하루의 난이도는 그날 수행한 작업의 최대 난이도입니다.

따라서 taskDifficulty라는 정수 배열과 정수 d가 있습니다. i번째 작업의 난이도는 taskDifficulty[i]입니다. 작업 일정의 최소 난이도를 찾아야 합니다. 작업 일정을 찾을 수 없으면 -1을 반환합니다.

따라서 입력이 taskDifficulty =[6,5,4,3,2,1], d =2,

그러면 출력은 7이 됩니다. 첫째 날에는 처음 5개의 작업을 완료할 수 있고 총 난이도는 6입니다. 이제 2일에는 마지막 작업을 완료할 수 있고 총 난이도는 1이므로 일정의 난이도는 다음과 같습니다. 6 + 1 =7.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve() 함수를 정의하면 배열 v, idx, k, 하나의 2D dp,

• idx가 v의 크기와 같고 k가 0과 같으면 -

  • 0 반환

• k <0 또는 idx가 v 및 k> 0의 크기와 같으면 -

  • 1^6 반환

• dp[idx, k]가 -1과 같지 않으면 -

  • 반환 dp[idx, k]

• maxVal :=0

• ret :=inf

• initialize i :=idx의 경우, i

  • maxVal :=v[i] 및 maxVal의 최대값

  • ret :=ret 및 maxVal의 최소값 + solve(v, i + 1, k - 1, dp)

• dp[idx, k] :=ret

• 리턴 렛

• 주요 방법에서 다음을 수행하십시오 -

• n :=j의 크기

• d> n이면 -

  • 반환 -1

• n x (d + 1) 크기의 2D 배열 dp 하나를 정의하고 이것을 -1로 채웁니다.

• 해결(j, 0, d, dp)을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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));
}

입력

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

출력

7