資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式：查詢完成 k 天內工作所需的最小難度總和
假設我們有一個名為 jobs 的數字列表和另一個值 k。現在我們希望在 k 個不同的天內完成所有工作。工作必須按給定的順序執行，並且每天必須完成一項任務。工作 i 的難度儲存在 jobs[i] 中，在一整天完成工作列表的難度將是在那一天執行的最難工作的難度。因此，我們必須找到在 k 個不同天內執行工作的最小難度總和。
因此，如果輸入類似於 jobs = [2, 3, 4, 6, 3] k = 2，則輸出將為 8，首先我們執行 [2]，然後執行 [3, 4, 6, 3]。因此難度為 2 + (3, 4, 6, 3) 的最大值 = 8。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個大小為 505 x 15 的陣列 dp。
- 定義一個函式 dfs()，它將接收 start、k 和一個數組 v，
- 如果 start >= v 的大小，則：
- 返回（如果 k 等於 0，則返回 0，否則返回無窮大）
- 如果 k < 0，則：
- 返回無窮大
- 如果 dp[start, k] 不等於 -1，則：
- 返回 dp[start, k]
- ret := 無窮大
- val := 0
- 從 i := start 初始化，當 i < v 的大小，更新（增加 i 的值 1），執行：
- val := val 和 v[i] 的最大值
- ret := ret 和 (val + dfs(i + 1, k - 1, v)) 的最小值
- dp[start, k] = ret
- 返回 ret
- 從主方法執行以下操作：
- 用 -1 填充 dp
- 返回 dfs(0, k, jobs)
示例（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
更新於： 2020-12-12
126 次檢視
廣告