- #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;
- }