思路

使用费用提前计算的思想, 考虑当前批的子任务, 所需要的启动时间S, 该启动时间会累计到此后所有任务的完成时刻.
状态定义
f[i]表示将前i个任务分成若干批执行的最小费用
转移方程
f[i]=min(f[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[N]-sumC[j])
其中第j+1至i个任务在同一批次内完成

算法设计

设置二重循环, 时间复杂度为$O(N^2)$

循环1: 设置子批次以第i个任务为结尾
    循环2: 设置子批次以第j个任务为开始, 其中0<j<i-1
        f[i]=min(f[i], 转移方程计算结果)

c++

#include <bits/stdc++.h>
using namespace std;

const int N=5005;
int n, s;
int sumt[N], sumc[N];
int f[N];

int main(){
    memset(f, 0x3f, sizeof f);
    memset(sumt, 0x00, sizeof sumt);
    memset(sumc, 0x00, sizeof sumc);
    cin>>n>>s;
    for(int i=1; i<=n; ++i){
        int t, c;
        cin>>t>>c;
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    f[0]=0;
    for(int i=1; i<=n; ++i)
        for(int j=0; j<i; ++j)
            f[i]=min(f[i], f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]));
    cout<<f[n]<<endl;
    return 0;
}

python

from typing import List
class Solution:
    def main(self, n:int, s:int):
        INF=float('inf')
        f=[INF for _ in range(n+1)]
        sumc, sumt = [0 for _ in range(n+1)], [0 for _ in range(n+1)]
        for i in range(1, n+1):
            t, c=map(int, input().split())
            sumt[i]=sumt[i-1]+t
            sumc[i]=sumc[i-1]+c
        f[0]=0
        for i in range(1, n+1):
            for j in range(i):
                f[i]=min(f[i], f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]))
        print(f[n])

if __name__ == '__main__':
    n=int(input())
    s=int(input())
    sol=Solution()
    sol.main(n, s)