โปรแกรมค้นหาผลรวมของความยากลำบากขั้นต่ำในการทำงานให้เสร็จภายใน k วันใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่างานและอีกค่าหนึ่งคือ k ตอนนี้เราต้องการทำงานทั้งหมดให้เสร็จภายใน k วันที่ต่างกัน งานจะต้องดำเนินการตามลำดับที่กำหนดและในแต่ละวันเราต้องทำงานให้เสร็จหนึ่งงาน ความยากของงาน i ถูกเก็บไว้ที่งาน[i] และความยากในการกรอกรายการงานในหนึ่งวันจะเป็นงานที่ยากที่สุดที่ทำในวันนั้น ดังนั้นเราจึงต้องหาผลรวมขั้นต่ำของความยากลำบากในการทำงานในช่วง k วันที่แตกต่างกัน

ดังนั้น ถ้าอินพุตเหมือนกับงาน =[2, 3, 4, 6, 3] k =2 ผลลัพธ์จะเป็น 8 ตอนแรกเราทำ [2] แล้วทำ [3, 4, 6, 3] ความยากคือ 2 + สูงสุด (3, 4, 6, 3) =8

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ dp ขนาด:505 x 15
• กำหนดฟังก์ชัน dfs() ซึ่งจะเริ่มต้น k และอาร์เรย์ v
• ถ้า start>=ขนาดของ v แล้ว −
  • ผลตอบแทน (ถ้า k เหมือนกับ 0, แล้ว 0, มิฉะนั้น inf)
• ถ้า k <0 แล้ว −
  • ผลตอบแทน
• ถ้า dp[start, k] ไม่เท่ากับ -1 แล้ว −
  • ส่งคืน dp[start, k]
• ret :=inf
• ค่า :=0
• สำหรับการเริ่มต้น i :=start เมื่อ i
• val :=สูงสุดของ val และ v[i]
• ret :=ขั้นต่ำของ ret และ (val + dfs(i + 1, k - 1, v))

ตัวอย่าง (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