A22623. 搬运水果
填空题
困难
知识点
题目描述
搬运水果
题目描述
在果园里，n 堆果实排成一个环形，第 i 堆果实的重量为 ai。果农需要将所有果实合并成一堆。合并规则如下：
（1）每次只能合并相邻的两堆，新堆的重量为两堆重量之和；
（2）每次合并消耗的体力等于新堆的重量；
（3）合并后新堆与剩余堆仍保持环形排列。
请设计合并顺序，求出合并全过程消耗的最小总体力与最大总体力。
输入格式
第一行：整数 n，表示果实堆数；
第二行：n 个整数 a1、a2、……、an，表示每堆果实的重量。
输出格式
第一行：最小总体力消耗；
第二行：最大总体力消耗。
输入样例
4
4 5 9 4输出样例
43
54数据范围：
1≤n≤100，1≤ai≤1000。
参考答案
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(2 * n + 1, 0);
vector<int> prefix(2 * n + 1, 0);
// 读取输入并构建环形数组（复制一份接在末尾）
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
// 计算前缀和
for (int i = 1; i <= 2 * n; i++) {
prefix[i] = prefix[i - 1] + a[i];
}
// DP数组初始化
vector<vector<int>> dp_min(2 * n + 1, vector<int>(2 * n + 1, INT_MAX));
vector<vector<int>> dp_max(2 * n + 1, vector<int>(2 * n + 1, 0));
// 初始化单个区间
for (int i = 1; i <= 2 * n; i++) {
dp_min[i][i] = 0;
dp_max[i][i] = 0;
}
// 区间DP计算
for (int len = 2; len <= n; len++) { // 区间长度
for (int l = 1; l <= 2 * n - len + 1; l++) { // 左端点
int r = l + len - 1; // 右端点
for (int k = l; k < r; k++) { // 分割点
int sum = prefix[r] - prefix[l - 1];
dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] + dp_min[k + 1][r] + sum);
dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] + dp_max[k + 1][r] + sum);
}
}
}
// 在环形中找最小值和最大值
int min_cost = INT_MAX;
int max_cost = 0;
for (int i = 1; i <= n; i++) {
min_cost = min(min_cost, dp_min[i][i + n - 1]);
max_cost = max(max_cost, dp_max[i][i + n - 1]);
}
cout << min_cost << endl;
cout << max_cost << endl;
return 0;
}
上一题
下一题