ความยากขั้นต่ำของตารางงานในภาษา C++

สมมติว่าเราต้องการกำหนดเวลารายการงานใน 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