โปรแกรมหาความยากรวมต่ำสุดทำงาน k วันใน C++

ให้ jobs[] ความยากแต่ละงาน และ k วัน ต้องทำงานตามลำดับ วันละอย่างน้อย 1 งาน ความยากของวัน = max ความยากงานในวันนั้น หาผลรวมความยากน้อยสุด

ตัวอย่าง: jobs=[2,3,4,6,3], k=2 → 8 วันที่ 1: [2] (max=2), วันที่ 2: [3,4,6,3] (max=6) รวม 8

ขั้นตอนการแก้ปัญหา (DP + Memoization)

1. dp[start][k] = คำตอบสำหรับ jobs[start..] เหลือ k วัน
2. dfs(start, k):
   • ถ้า start >= n: คืน (k==0 ? 0 : inf)
   • ถ้า k < 0: คืน inf
   • val = 0, ret = inf
   • วน i = start ถึง n-1:
     • val = max(val, jobs[i])
     • ret = min(ret, val + dfs(i+1, k-1))
   • dp[start][k] = ret

ตัวอย่างโค้ด 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, 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};
    cout << solve(v, 2); // 8
    return 0;
}

อินพุต

{2, 3, 4, 6, 3}, 2

เอาต์พุต

8