携程网站建设的意义,智能模板网站建设价格,青岛app网站开发,做外贸用哪个网站好1. 题目
你需要制定一份 d 天的工作计划表。工作之间存在依赖#xff0c;要想执行第 i 项工作#xff0c;你必须完成全部 j 项工作#xff08; 0 j i#xff09;。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和#xff0c;而一天…1. 题目
你需要制定一份 d 天的工作计划表。工作之间存在依赖要想执行第 i 项工作你必须完成全部 j 项工作 0 j i。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的 最小难度 。如果无法制定工作计划则返回 -1 。
示例 1
输入jobDifficulty [6,5,4,3,2,1], d 2
输出7
解释第一天您可以完成前 5 项工作总难度 6.
第二天您可以完成最后一项工作总难度 1.
计划表的难度 6 1 7 示例 2
输入jobDifficulty [9,9,9], d 4
输出-1
解释就算你每天完成一项工作仍然有一天是空闲的
你无法制定一份能够满足既定工作时间的计划表。示例 3
输入jobDifficulty [1,1,1], d 3
输出3
解释工作计划为每天一项工作总难度为 3 。示例 4
输入jobDifficulty [7,1,7,1,7,1], d 3
输出15示例 5
输入jobDifficulty [11,111,22,222,33,333,44,444], d 6
输出843提示
1 jobDifficulty.length 300
0 jobDifficulty[i] 1000
1 d 10来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-difficulty-of-a-job-schedule 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. DP解题
class Solution {
public:int minDifficulty(vectorint jobDifficulty, int d) {int n jobDifficulty.size(), i, j, k, MAX 0;if(n d)return -1;vectorvectorint dp(d,vectorint(n, INT_MAX));for(i 0; i n-d; i){MAX max(MAX, jobDifficulty[i]);dp[0][i] MAX;//初始化第一天的工作难度的几种可能}for(i 1; i d; i)//填表剩余的几天{ //每次前一天至少完成一项工作还要保证后面几天至少每天有1项工作要做for(j i; j n-di; j){ MAX 0;for(k j; k n-di; k){ //对前一天和当前天的所有组合取min难度MAX max(MAX, jobDifficulty[k]);dp[i][k] min(dp[i][k], MAXdp[i-1][j-1]);}}}return dp[d-1][n-1];}
};示例 5
输入jobDifficulty [11,111,22,222,33,333,44,444], d 6
输出843填写dp状态表过程
1111122222333334444411111111122122、133233、333、333144344、344344、344、266366366、377477、677、599399699、699699、699、521732732、743 843、1143、965
倒推回去应该这么分成6天 11 | 111 | 22 | 222 | 33 | 333、44、444 总的难度最小11 111 22 222 33 444 843
