d일에 작업 목록을 예약하려고 한다고 가정합니다. 작업은 종속적이므로 i 번째 작업을 수행하려면 0 <=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