本文共 1678 字，大约阅读时间需要 5 分钟。

题目大意：有N个任务，要求依次执行，每个任务有相应的执行时间和影响因素

你可以将多个任务划分到一个模块，也可以将一个任务划分到一个模块，模块完成的时间就是(该模块的所有任务的时间和 + T)，模块完成时间就是模块内所有任务的完成时间 每个任务完成的代价是任务完成时间*该任务影响因素 问所有任务都完成后，sum(任务完成时间*该任务影响因素)的最小值

解题思路：这题要倒着DP，任务顺序对调，第一个任务变成最后一个任务

设dp[i]为从第i个任务执行到最后一个任务所需花费的最小代价(因为是倒着进行DP的，最后一个任务变成了第一个，就相当于第一个任务到第i个任务完成所需要花费的最小代价)，这里假设影响因素和为sumF,时间总和为sumT 则dp[i] = dp[j] + (sumT[i] - sumT[j] + T) * sumF[i] 假设k > j,且点k比点j优 则 dp[j] + (sumT[i] - sumT[j] + T) * sumF[i] >= dp[k] + (sumT[i] - sumT[k] + T) * sumF[i] 化简得 sumF[i] >= (dp[k] - dp[j]) / (sumT[k] - sumT[j]) 因为sumF[i]随着i的增大而递增，所以得到斜率方程

#include 
   
    #include 
    
     const int N = 10010;typedef long long LL;int n, s;LL sumF[N], sumT[N], dp[N], que[N];void init() {    for (int i = 1; i <= n; i++)        scanf("%lld%lld", &sumT[i], &sumF[i]);    for (int i = n - 1; i >= 1; i--) {        sumT[i] += sumT[i + 1];        sumF[i] += sumF[i + 1];    }}LL getUp(int j, int k) {    return dp[j] - dp[k];}LL getDown(int j, int k) {    return sumT[j] - sumT[k];}void getDp(int i, int k) {    dp[i] = dp[k] + (s + sumT[i] - sumT[k]) * (sumF[i]);}void solve() {    int head, tail;    head = tail = 0;    que[tail++] = n + 1;    for (int i = n; i > 0; i--) {        while (head + 1 < tail && getUp(que[head + 1], que[head]) <= getDown(que[head + 1], que[head]) * sumF[i])            head++;        getDp(i, que[head]);        while (head + 1 < tail && getUp(i, que[tail - 1]) * getDown(que[tail - 1], que[tail - 2]) <= getUp(que[tail - 1], que[tail - 2]) * getDown(i, que[tail - 1]))            tail--;        que[tail++] = i;    }    printf("%lld\n", dp[1]);}int main() {    while (scanf("%d%d", &n, &s) != EOF) {        init();        solve();    }    return 0;}
    
   

转载地址：https://blog.csdn.net/L123012013048/article/details/48948653 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！