asp.net 发布网站 ftp,空间租用网站模板,途牛网站建设,营销型网站建设专家[NOI1995] 石子合并
题目描述
在一个圆形操场的四周摆放 N N N 堆石子#xff0c;现要将石子有次序地合并成一堆#xff0c;规定每次只能选相邻的 2 2 2 堆合并成新的一堆#xff0c;并将新的一堆的石子数#xff0c;记为该次合并的得分。
试设计出一个算法,计算出将 …[NOI1995] 石子合并
题目描述
在一个圆形操场的四周摆放 N N N 堆石子现要将石子有次序地合并成一堆规定每次只能选相邻的 2 2 2 堆合并成新的一堆并将新的一堆的石子数记为该次合并的得分。
试设计出一个算法,计算出将 N N N 堆石子合并成 1 1 1 堆的最小得分和最大得分。
输入格式
数据的第 1 1 1 行是正整数 N N N表示有 N N N 堆石子。
第 2 2 2 行有 N N N 个整数第 i i i 个整数 a i a_i ai 表示第 i i i 堆石子的个数。
输出格式
输出共 2 2 2 行第 1 1 1 行为最小得分第 2 2 2 行为最大得分。
样例 #1
样例输入 #1
4
4 5 9 4样例输出 #1
43
54提示 1 ≤ N ≤ 100 1\leq N\leq 100 1≤N≤100 0 ≤ a i ≤ 20 0\leq a_i\leq 20 0≤ai≤20。
题目大意
在一个圆形操场的四周摆放了 N N N 堆石子。每次操作中你只能选择相邻的两堆石子进行合并并且合并的得分是这两堆石子的数量之和。最终的目标是将所有石子合并为一堆要求你计算出合并过程中得到的最小得分和最大得分。
解题思路
这道题目涉及到动态规划Dynamic Programming, DP和圆形排列的处理。我们可以将圆形的石子排列“展平”成一条线并使用动态规划解决合并过程中的最小得分和最大得分问题。具体步骤如下 展平圆形结构由于石子的排列是圆形的我们可以通过将数组复制一遍并拼接起来变成一个长度为 2 N 2N 2N 的数组。这样我们就可以将圆形结构当作一个线性结构来处理。 动态规划状态定义 dp1[l][r]表示在区间 [ l , r ] [l, r] [l,r] 内合并所有石子的最小得分。dp2[l][r]表示在区间 [ l , r ] [l, r] [l,r] 内合并所有石子的最大得分。 状态转移方程 计算最小得分时我们可以选择区间内的任意一个位置进行合并更新dp1[l][r] [ dp1[l][r] \min(dp1[l][r], dp1[l][k] dp1[k1][r] sum[r] - sum[l-1]) ]同样地计算最大得分时更新dp2[l][r] [ dp2[l][r] \max(dp2[l][r], dp2[l][k] dp2[k1][r] sum[r] - sum[l-1]) ] 前缀和的计算为了更快速地计算区间和我们可以使用一个sum数组其中sum[i]表示从第一个石子到第 i i i 个石子的总和。 最终结果由于是一个环形结构我们需要对dp1和dp2中所有可能的区间长度为 N N N 的子区间计算最小值和最大值。
代码分析
#include bits/stdc.h
#include iostream
#include algorithm
using namespace std;const int inf 1e9 7;
const int N 300 10;int n;
int dp1[N][N]; // 最小得分 DP
int dp2[N][N]; // 最大得分 DP
int sum[N]; // 前缀和数组
vectorint v(N); // 石子的数量void clear() {for (int i 0; i N; i) {for (int j i; j N; j) {if (i j) {dp1[i][j] 0;dp2[i][j] 0;} else {dp1[i][j] inf;dp2[i][j] -inf;}}}
}void solved() {clear();cin n; // 读入石子的堆数for (int i 1; i n; i) {cin v[i];sum[i] sum[i - 1] v[i]; // 计算前缀和}// 扩展石子数组处理圆形结构for (int i n 1; i 2 * n; i) {v[i] v[i - n];sum[i] sum[i - 1] v[i];}// 计算 dp 数组for (int len 2; len n; len) { // 长度从2到nfor (int l 1; l 2 * n - len 1; l) { // 枚举区间起始位置int r l len - 1; // 区间的右端for (int k l; k r; k) { // 枚举分割点dp1[l][r] min(dp1[l][r], dp1[l][k] dp1[k 1][r] sum[r] - sum[l - 1]);dp2[l][r] max(dp2[l][r], dp2[l][k] dp2[k 1][r] sum[r] - sum[l - 1]);}}}int minn inf, maxx -inf;for (int l 1; l n; l) { // 最终结果遍历所有可能的起始位置minn min(minn, dp1[l][l n - 1]);maxx max(maxx, dp2[l][l n - 1]);}cout minn endl; // 输出最小得分cout maxx endl; // 输出最大得分
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T 1;while (T--) {solved();}
}
代码分析 初始化和前缀和首先初始化 dp1 和 dp2 数组dp1[i][j] 用于保存区间 [ i , j ] [i, j] [i,j] 的最小合并得分dp2[i][j] 用于保存区间 [ i , j ] [i, j] [i,j] 的最大合并得分。我们也通过 sum 数组计算了从第一个石子到第 i i i 个石子的前缀和。 展开圆形数组由于问题中石子是圆形排列的我们通过将数组从头到尾复制一次形成一个长度为 2 N 2N 2N 的新数组 v并且更新对应的前缀和 sum。 动态规划计算通过枚举区间长度 len 和起始位置 l以及每个区间内的分割点 k使用状态转移方程更新 dp1 和 dp2 数组。最终通过遍历所有可能的区间找到最小得分和最大得分。 时间复杂度由于有三重循环区间长度、区间起点、分割点时间复杂度为 O ( N 3 ) O(N^3) O(N3)。对于 N ≤ 100 N \leq 100 N≤100这种复杂度是可以接受的。
总结
这个问题的核心在于如何利用动态规划求解合并石子的最小和最大得分。通过将圆形结构展开为线性结构可以简化问题的求解。算法通过动态规划计算每个区间的最小和最大得分并最终遍历所有可能的区间来求解答案。
