Giả sử chúng ta có một danh sách các số được gọi là công việc và một giá trị khác k. Bây giờ chúng tôi muốn hoàn thành tất cả các công việc trong k ngày khác nhau. Các công việc phải được thực hiện theo thứ tự đã cho và mỗi ngày chúng ta phải hoàn thành một công việc. Khó khăn của công việc i được lưu trữ tại các công việc [i] và khó khăn trong việc hoàn thành danh sách công việc vào một ngày sẽ là công việc có độ khó tối đa được thực hiện vào ngày đó. Vì vậy, chúng ta phải tìm tổng số khó khăn tối thiểu để thực hiện công việc trong k ngày khác nhau.
Vì vậy, nếu đầu vào giống như công việc =[2, 3, 4, 6, 3] k =2, thì đầu ra sẽ là 8, lúc đầu chúng ta làm [2] sau đó làm [3, 4, 6, 3]. vì vậy độ khó là 2 + tối đa là (3, 4, 6, 3) =8.
Để 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 mảng dp có kích thước:505 x 15.
- Xác định một hàm dfs (), hàm này sẽ bắt đầu, k và một mảng v,
- nếu bắt đầu> =kích thước của v, thì -
- return (nếu k giống 0 thì 0, ngược lại là inf)
- nếu k <0, thì -
- thông tin trở lại
- nếu dp [start, k] không bằng -1, thì -
- return dp [start, k]
- ret:=inf
- val:=0
- để khởi tạo i:=start, khi i
- val:=tối đa là val và v [i]
- ret:=tối thiểu ret và (val + dfs (i + 1, k - 1, v))
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
{2, 3, 4, 6, 3}, 2 Đầu ra
8