原始问题:
任务分配与编辑时间优化策略
测试用例的数量)。接下来的T行,每行包含两个整数n和k,分别表示任务总数和小明选取的任务数。然后是n行,每行一个整数ti,表示第i个任务的编辑时间。
输出描述:对于每个测试用例,输出一个整数,表示小明和小白完成编辑所需的最短时间。如果无法完成编辑,则输出-1。
解析:这是一个动态规划问题。我们可以使用dpi表示前i个任务中,小明选取j个任务时的最短编辑时间。状态转移方程为:
dpi = max(dpi-1, dpi-1) + max(t[i], ti)
其中,dp0 = 0,其他状态初始化为正无穷大。最后,遍历所有状态,找到最小值即可。
代码实现如下:
def min_edit_time(T, test_cases):
dp = [[float('inf')] * (k + 1) for _ in range(len(test_cases))]
dp[0][0] = 0
for i in range(len(test_cases)):
n, k = test_cases[i]
tasks = [int(x) for x in input().split()]
t = sorted(tasks, reverse=True)
for j in range(k + 1):
for p in range(i, n):
dp[p + 1][j] = min(dp[p + 1][j], dp[p][j - 1]) + max(t[p], tasks[p])
if j < k:
dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]) + max(t[i], tasks[i])
for i in range(len(test_cases), len(dp)):
if dp[i][k] != float('inf'):
return dp[i][k]
return -1
Prev:"筛选子序列:满足特定连续数条件的和(模10^9+7)"