สมมติว่าเราต้องการกำหนดเวลารายการงานใน d วัน งานขึ้นอยู่กับดังนั้นในการทำงานกับงานที่ i-th เราจะต้องเสร็จสิ้นงานทั้งหมด j โดยที่ 0 <=j
เราต้องทำงานให้เสร็จอย่างน้อยหนึ่งงานในแต่ละวัน ความยากของตารางงานคือผลรวมของความยากลำบากในแต่ละวันของจำนวนวัน ความยากของวันคือความยากสูงสุดของงานที่ทำในวันนั้น
ดังนั้นเราจึงมีอาร์เรย์ของจำนวนเต็มที่เรียกว่า 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, 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
-
สำหรับการเริ่มต้น i :=idx เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -
-
maxVal :=สูงสุดของ v[i] และ maxVal
-
ret :=ขั้นต่ำ ret และ maxVal + แก้ปัญหา (v, i + 1, k - 1, dp)
-
-
dp[idx, k] :=ยกเลิก
-
รีเทิร์น
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
n :=ขนาดของ j
-
ถ้า d> n แล้ว −
-
กลับ -1
-
-
กำหนดอาร์เรย์ 2 มิติ dp หนึ่งขนาด n x (d + 1) และเติมด้วย -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