job이라는 숫자 목록과 또 다른 값 k가 있다고 가정합니다. 이제 우리는 k개의 다른 날에 모든 작업을 끝내고 싶습니다. 작업은 주어진 순서대로 수행되어야 하며 매일 하나의 작업을 완료해야 합니다. 작업 i의 난이도는 작업[i]에 저장되며 하루에 작업 목록을 완료하는 난이도는 그날 수행한 최대 난이도 작업이 됩니다. 따라서 우리는 k일 동안 작업을 수행하는 데 어려움의 최소 합을 찾아야 합니다.
따라서 입력이 작업 =[2, 3, 4, 6, 3] k =2와 같으면 출력은 8이 됩니다. 처음에는 [2]를 수행한 다음 [3, 4, 6, 3]을 수행합니다. 따라서 난이도는 2 + 최대 (3, 4, 6, 3) =8입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 505 x 15 크기의 배열 dp를 정의합니다.
- dfs() 함수를 정의하면 시작, k, 배열 v가 필요합니다.
- 시작>=v의 크기이면 -
- 반환(k가 0과 같으면 0, 그렇지 않으면 inf)
- k <0이면 -
- 반환 정보
- dp[start, k]가 -1과 같지 않으면 -
- dp[start, k]를 반환
- ret :=inf
- 값:=0
- 초기화 i :=시작, i
- val :=val 및 v[i]의 최대값
- ret :=ret의 최소값 및 (val + dfs(i + 1, k - 1, v))
예시(C++)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6;
int dp[505][15];
int dfs(int start, int k, vector <int>& v){
if(start >= v.size()){
return k == 0 ? 0 : inf;
}
if(k < 0)
return inf;
if(dp[start][k] != -1)
return dp[start][k];
int ret = inf;
int val = 0;
for(int i = start; i < v.size(); i++){
val = max(val, v[i]);
ret = min(ret, val + dfs(i + 1, k - 1, v));
}
return dp[start][k] = ret;
}
int solve(vector<int>& jobs, int k) {
memset(dp ,-1, sizeof dp);
return dfs(0, k, jobs);
}
int main(){
vector<int> v = {2, 3, 4, 6, 3};
int k = 2;
cout << solve(v, k);
} 입력
{2, 3, 4, 6, 3}, 2 출력
8