資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中作業排程的最小難度
假設我們想在 d 天內安排一系列任務。這些任務是相互依賴的，因此要進行第 i 個任務，必須完成所有 0 <= j < i 的任務。
我們必須在每一天至少完成一項任務。任務排程的難度實際上是 d 天中每一天難度的總和。一天的難度是那天完成的任務中難度最大的任務的難度。
因此，我們有一個名為 taskDifficulty 的整數陣列和一個整數 d。第 i 個工作的難度是 taskDifficulty[i]。我們必須找到任務排程的最小難度。如果我們找不到任務的排程，則返回 -1。
因此，如果輸入類似於 taskDifficulty = [6,5,4,3,2,1]，d = 2，
則輸出將為 7，因為在第 1 天我們可以完成前 5 個工作，總難度為 6。現在在第 2 天我們可以完成最後一個工作，總難度為 1，因此排程的難度將為 6 + 1 = 7。
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 solve()，它將接收一個數組 v、idx、k 和一個二維 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
從初始化 i := idx 開始，當 i < v 的大小，更新（將 i 增加 1），執行 -
maxVal := v[i] 和 maxVal 的最大值
ret := ret 和 maxVal + solve(v, i + 1, k - 1, dp) 的最小值
dp[idx, k] := ret
返回 ret
從主方法執行以下操作 -
n := j 的大小
如果 d > n，則 -
返回 -1
定義一個大小為 n x (d + 1) 的二維陣列 dp 並將其填充為 -1
返回 solve(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
314 次瀏覽
