简答题
偏难
#13126
搬运水果 在果园里,n 堆果实排成一个环形,第 i 堆果实的重量为 a i 。果农需要将所有果实合并成一堆。合并规则如下: (1)每次只能合并相邻的两堆,新堆的…
搬运水果
在果园里,n 堆果实排成一个环形,第 i 堆果实的重量为 ai。果农需要将所有果实合并成一堆。合并规则如下:
(1)每次只能合并相邻的两堆,新堆的重量为两堆重量之和;
(2)每次合并消耗的体力等于新堆的重量;
(3)合并后新堆与剩余堆仍保持环形排列。
请设计合并顺序,求出合并全过程消耗的最小总体力与最大总体力。
时间限制:1000ms内存限制:256MB
输入格式
第一行:整数 n,表示果实堆数;
第二行:n 个整数 a1、a2、……、an,表示每堆果实的重量。
输出格式
第一行:最小总体力消耗;
第二行:最大总体力消耗。
输入样例
4 4 5 9 4
输出样例
43 54
数据范围:
1≤n≤100,1≤ai≤1000。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
const int INF = INT_MAX / 2; // 避免溢出
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n == 1) { // 只有一堆,无需合并
cout << 0 << endl;
cout << 0 << endl;
return 0;
}
// 将环形转为线性,扩展数组为2n长度
vector<int> b(2 * n);
for (int i = 0; i < 2 * n; ++i) {
b[i] = a[i % n];
}
// 计算前缀和,s[0] = 0, s[i] = b[0] + ... + b[i-1]
vector<int> s(2 * n + 1, 0);
for (int i = 1; i <= 2 * n; ++i) {
s[i] = s[i - 1] + b[i - 1];
}
// 初始化动态规划数组
vector<vector<int>> min_dp(2 * n, vector<int>(2 * n, 0));
vector<vector<int>> max_dp(2 * n, vector<int>(2 * n, 0));
// 填充dp数组,l为合并的堆数(从2到n)
for (int l = 2; l <= n; ++l) { // l表示当前合并的堆数
for (int i = 0; i + l - 1 < 2 * n; ++i) { // i为起始位置
int j = i + l - 1; // j为结束位置
// 初始化当前区间的最小和最大值
min_dp[i][j] = INF;
max_dp[i][j] = 0;
int sum_ij = s[j + 1] - s[i]; // i到j的总重量
// 尝试所有可能的拆分点k
for (int k = i; k < j; ++k) {
// 更新最小值
min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k + 1][j] + sum_ij);
// 更新最大值
max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k + 1][j] + sum_ij);
}
}
}
// 寻找环形结构的最小和最大体力消耗(所有可能的起始位置)
int min_total = INF;
int max_total = 0;
for (int i = 0; i < n; ++i) {
min_total = min(min_total, min_dp[i][i + n - 1]);
max_total = max(max_total, max_dp[i][i + n - 1]);
}
cout << min_total << endl;
cout << max_total << endl;
return 0;
}</pre>
这道题暂未补解析。