数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序：查找完成 k 天内工作所需的最小难度总和
假设我们有一个名为 jobs 的数字列表和另一个值 k。现在我们希望在 k 个不同的天内完成所有工作。工作必须按给定的顺序执行，并且每天必须完成一项任务。工作 i 的难度存储在 jobs[i] 中，在一整天完成工作列表的难度将是在那一天执行的最难工作的难度。因此，我们必须找到在 k 个不同天内执行工作的最小难度总和。
因此，如果输入类似于 jobs = [2, 3, 4, 6, 3] k = 2，则输出将为 8，首先我们执行 [2]，然后执行 [3, 4, 6, 3]。因此难度为 2 + (3, 4, 6, 3) 的最大值 = 8。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个大小为 505 x 15 的数组 dp。
- 定义一个函数 dfs()，它将接收 start、k 和一个数组 v，
- 如果 start >= v 的大小，则：
- 返回（如果 k 等于 0，则返回 0，否则返回无穷大）
- 如果 k < 0，则：
- 返回无穷大
- 如果 dp[start, k] 不等于 -1，则：
- 返回 dp[start, k]
- ret := 无穷大
- val := 0
- 从 i := start 初始化，当 i < v 的大小，更新（增加 i 的值 1），执行：
- val := val 和 v[i] 的最大值
- ret := ret 和 (val + dfs(i + 1, k - 1, v)) 的最小值
- dp[start, k] = ret
- 返回 ret
- 从主方法执行以下操作：
- 用 -1 填充 dp
- 返回 dfs(0, k, jobs)
示例（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
更新于： 2020-12-12
126 次查看
广告