首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;climits&gt; using namespace std; int main() {     int n;     cin &gt;&gt; n;     vector&lt;int&gt; a(2 * n + 1, 0);     vector&lt;int&gt; prefix(2 * n + 1, 0);          // 读取输入并构建环形数组(复制一份接在末尾)     for (int i = 1; i &lt;= n; i++) {         cin &gt;&gt; a[i];         a[i + n] = a[i];     }          // 计算前缀和     for (int i = 1; i &lt;= 2 * n; i++) {         prefix[i] = prefix[i - 1] + a[i];     }          // DP数组初始化     vector&lt;vector&lt;int&gt;&gt; dp_min(2 * n + 1, vector&lt;int&gt;(2 * n + 1, INT_MAX));     vector&lt;vector&lt;int&gt;&gt; dp_max(2 * n + 1, vector&lt;int&gt;(2 * n + 1, 0));          // 初始化单个区间     for (int i = 1; i &lt;= 2 * n; i++) {         dp_min[i][i] = 0;         dp_max[i][i] = 0;     }          // 区间DP计算     for (int len = 2; len &lt;= n; len++) {  // 区间长度         for (int l = 1; l &lt;= 2 * n - len + 1; l++) {  // 左端点             int r = l + len - 1;  // 右端点             for (int k = l; k &lt; 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 &lt;= 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 &lt;&lt; min_cost &lt;&lt; endl;     cout &lt;&lt; max_cost &lt;&lt; endl;          return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;climits&gt; #include &lt;algorithm&gt; using namespace std; const int INF = INT_MAX / 2; // 避免溢出 int main() {     int n;     cin &gt;&gt; n;     vector&lt;int&gt; a(n);     for (int i = 0; i &lt; n; ++i) {         cin &gt;&gt; a[i];     }          if (n == 1) { // 只有一堆,无需合并         cout &lt;&lt; 0 &lt;&lt; endl;         cout &lt;&lt; 0 &lt;&lt; endl;         return 0;     }          // 将环形转为线性,扩展数组为2n长度     vector&lt;int&gt; b(2 * n);     for (int i = 0; i &lt; 2 * n; ++i) {         b[i] = a[i % n];     }          // 计算前缀和,s[0] = 0, s[i] = b[0] + ... + b[i-1]     vector&lt;int&gt; s(2 * n + 1, 0);     for (int i = 1; i &lt;= 2 * n; ++i) {         s[i] = s[i - 1] + b[i - 1];     }          // 初始化动态规划数组     vector&lt;vector&lt;int&gt;&gt; min_dp(2 * n, vector&lt;int&gt;(2 * n, 0));     vector&lt;vector&lt;int&gt;&gt; max_dp(2 * n, vector&lt;int&gt;(2 * n, 0));          // 填充dp数组,l为合并的堆数(从2到n)     for (int l = 2; l &lt;= n; ++l) { // l表示当前合并的堆数         for (int i = 0; i + l - 1 &lt; 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 &lt; 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 &lt; 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 &lt;&lt; min_total &lt;&lt; endl;     cout &lt;&lt; max_total &lt;&lt; endl;          return 0; }</pre>
这道题暂未补解析。