561. Splitting the Work Across Days
Jobs must be done in the GIVEN ORDER over exactly d days. Each day must get at least one
job, and a day's difficulty is the HARDEST job done that day. The schedule's difficulty is
the sum over days.
Print the smallest achievable difficulty, or -1 if there are fewer jobs than days.
jobs 6 5 4 3 2 1, d = 2 -> 7 6 on day one, 5 4 3 2 1 on day two
jobs 9 9 9, d = 4 -> -1
## Why a day's cost is not additive
Every partition DP so far has had a day cost that grows as the block grows. Here it is a MAXIMUM, so adding a job to a day either changes nothing or jumps to the new job's difficulty.
That means you cannot decide greedily where to cut: a job that is cheap to append today may be exactly the job that would have made tomorrow expensive.
## The state
dp[i][g] = the smallest difficulty for the first i jobs done in g days
dp[0][0] = 0
dp[i][g] = min over p of dp[p][g-1] + max(jobs p..i-1)
where p runs over the positions where the last day could start.
## Keeping the maximum incremental
The inner term needs max(jobs[p..i-1]) for every p. Recomputing it is a third loop and
makes the whole thing O(n^3 d).
Walk p DOWNWARD from i-1 and carry the running maximum:
mx = 0
for p from i-1 down to g-2:
mx = max(mx, jobs[p])
relax dp[i][g] with dp[p][g-1] + mx
Extending the last day leftwards one job at a time is what lets the maximum be updated in
O(1), and it is the same incremental-aggregate move as problems 470 and 471.
## The bounds on p
The last day starts at p and the first p jobs must fill g-1 days, each non-empty. So
p >= g-1. And the last day must be non-empty, so p <= i-1.
Getting that lower bound wrong lets a day be empty, and the answer comes out too small. The
test 4 3 2 1 with d = 4 answers 10, which forces exactly one job per day, so any slack
in the bound shows immediately.
## Impossible
Fewer jobs than days means some day would be empty, so the answer is -1. That check comes
first, before the table is sized.
9 9 9 with d = 4 answers -1.
## Boundaries
d = 1 puts everything on one day, so the answer is the largest job. 1 1 1 with d = 1
answers 1.
d equal to the number of jobs gives one job per day, so the answer is the total. 4 3 2 1
with d = 4 answers 10.
Those two bracket the range of d.
## Cost
Time O(n^2 d). Space O(n d).
Constraints - `1 ≤ n ≤ 300` - `1 ≤ d ≤ 10` - `0 ≤ difficulty ≤ 1000`
Input
The first line contains two integers n and d.
The second line contains n job difficulties, in the order they must be done.
Output
Print the smallest schedule difficulty, or -1 if it is impossible.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.