任务安排 1

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 979 字

N个任务顺序分批，每批启动时间S，费用=完成

一本通
例

正文

/*
原题：任务安排 1（一本通 5.6 例 1）
题意：N 个任务顺序分批，每批启动时间 S，费用=完成时刻×系数，求最小总费用。
思路：前缀和 st/sc；dp[i]=min{dp[j]+(S+st[i]-st[j])*(sc[n]-sc[j])}，N≤5000 直接 O(N^2) 暴力。
复杂度：O(N^2) 时间 / O(N) 空间
易错点：用 sc[n]-sc[j]（含后面任务）而非 sc[i]，否则少算后续批次的 S 额外延迟。
易错点：枚举 j 从 0 开始，dp[0]=0 表示前 0 个任务费用为 0。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    long long S;
    if(!(cin >> N >> S)) return 0;
    vector<long long> st(N + 1, 0), sc(N + 1, 0);
    for(int i = 1; i <= N; i++){
        long long t, c;
        cin >> t >> c;
        st[i] = st[i - 1] + t;
        sc[i] = sc[i - 1] + c;
    }
    vector<long long> dp(N + 1, 0);
    for(int i = 1; i <= N; i++){
        long long best = LLONG_MAX;
        for(int j = 0; j < i; j++){
            long long cost = dp[j] + (S + st[i] - st[j]) * (sc[N] - sc[j]);
            if(cost < best) best = cost;
        }
        dp[i] = best;
    }
    cout << dp[N] << "\n";
    return 0;
}

任务安排 1

正文

一本通·提高篇的其它内容