C++ 动态规划。。。

#include 
#include 
using namespace std;
// 定义一个常量，表示无穷大
const int INF = 1e9;
int dp[1000 + 2];
 
// 定义一个函数，计算数组中某个区间的和
int sum(int arr[], int start, int end) {
    int s = 0;
    for (int i = start; i <= end; i++) {
        s += arr[i];
    }
    return s;
}
 
// 定义一个函数，解决最优批处理问题
int optimal_batch(int n, int S, int t[], int f[]) {
    // 定义一个数组，存储动态规划的结果
   
    // 初始化最后一个元素为0
    dp[1000 + 1] = 0;
    // 从后往前遍历每个作业
    for (int i = n; i >= 1; i--) {
        // 初始化dp[i]为无穷大
        dp[i] = INF;
        // 遍历所有可能的划分方式
        for (int j = i + 1; j <= n + 1; j++) {
            // 计算第一部分的总费用
            int cost = (S + sum(t, i, j - 1)) * sum(f, i, n);
            // 加上第二部分的最小总费用
            cost += dp[j];
            // 取最小值
            dp[i] = min(dp[i], cost);
        }
    }
    // 返回最终结果
    return dp[1];
}
 
// 主函数，测试样例
int main() {
    // 输入作业的数量和启动时间
    int n, S;
    cin >> n >> S;
    // 定义两个数组，存储每个作业的时间和费用系数
    int t[1000 + 1], f[1000 + 1];
    // 输入每个作业的时间和费用系数
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> f[i];
    }
    // 调用函数，求解最优批处理问题
    int ans = optimal_batch(n, S, t, f);
    // 输出结果
    cout << "最优批处理方案的总费用是：" << ans << endl;
    return 0;
}