问题描述： 在一台超级计算机上，编号为 1, 2, …, n 的 n 个作业等待批处理。批处理的任务就是将这 n 个作业分成若干批，每批包含相邻的若干作业。从时刻 0 开始，每批加工这些作业。在每批作业开始前，机器需要启动时间 S，而完成这批作业所需的时间是单独完成批中的每个作业需要时间的总和。单独完成第 i 个作业所需的时间是 $t_i$，所需的费用是它的完成时刻乘以一个费用系数 $f_i$。同一批作业将会在同一时刻完成。例如，如果在时刻 t 开始批作业 x, x+1, …, x+k，则这一批作业的完成时刻为 $t+S+(t_x + t_{x+1} + … + t_{x+k})$。最优批处理问题就是要确定总费用最小的批处理方案。

例如，假定有 5 个作业等待批处理，且
$S = 1, (t_1, t_2, t_3, t_4, t_5) = (1, 3, 4, 2, 1), (f_1, f_2, f_3, f_4, f_5) = (3, 2, 3, 4, 2)$
如果采用批处理方案 {1}, {2, 3}, {4, 5}，则各作业的完成时间分别为 (5, 5, 10, 14, 14)，各作业的费用分别为 (15, 10, 30, 42, 56)，因此，这个批处理方案总费用是 153。

算法设计： 对于给定的等待批处理的 n 个作业，计算其总费用最小的批处理方案。

数据输入： 由文件 input.txt 提供输入数据。文件的第 1 行是批处理作业数 n，第 2 行是启动时间 S。接下来每行有 2 个数，分别为单独完成第 i 个作业所需的时间 ti 和所需的费用系数 fi。

结果输出： 将计算出的最小总费用输出到文件 output.txt 中。

input.txt
5
1
1 3
3 2
4 3
2 3
1 4

output.txt
153

#include <iostream>
using namespace std;

/*
动态规划思路：
dp[i]表示从第i个任务开始到第n个任务（可以分好几批），所需要的最小费用
对于第i个任务，假设第i到第j-1的任务为第一批处理
st[j]是从第j到最后一个任务的处理时间总和（Σt）
sw[j]是从第j到最后一个任务的权重总和(Σw)
//这里可以理解为，一个任务的花费分成两部分，一部分是在运行前，一部分是在运行时；
1、启动批处理的固定费用是S
2、这一批次任务的完成时间在从i到j-1的任务处理时间的总和st[i]-st[j]
3、这一批任务的在这个时间内的费用为（S+完成时间）*(所有任务花费)    后面的任务虽然没有运行，但还是在耗费资源
dp[i]=min(z[j]+sw[i]*(S+st[i]-st[j]))    第一批任务花费加上后面所有任务的花费
*/

#define MAXN 100010
int n;//作业数
int S;//启动时间
int t[MAXN];//作业时间
int f[MAXN];//费用系数

int dp[MAXN];
int st[MAXN]={0};
int sw[MAXN]={0};

void init() {
    cin>>n;
    cin>>S;
    for(int i=0;i<n;i++){ cin>>t[i];
        cin>>f[i];
    }
    st[n]=0;
    st[n-1]=t[n-1];
    for(int i=n-2;i>=0;i--){
        st[i]=st[i+1]+t[i];
    }
    sw[n]=0;
    sw[n-1]=f[n-1];
    for(int i=n-2;i>=0;i--){
        sw[i]=sw[i+1]+f[i];
    }
    fill(dp,dp+n+1,0x7fffffff);//n+1
    dp[n]=0;//没有任务时花费为0
}

void solve(){
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<=n;j++){
            dp[i]=min(dp[i],dp[j]+sw[i]*(S+st[i]-st[j]));
        }
    }
    cout<<dp[0]<<endl;
}

int main() {
    init();
    solve();
    return 0;
}
/*
5
1
1 3
3 2
4 3
2 3
1 4
*/