张店网站建设定制爱站网是怎么回事

张店网站建设定制,爱站网是怎么回事,微信小程序开发教程从零开始,奇葩网站100个在算法领域#xff0c;石子合并问题是动态规划的经典应用场景#xff0c;而圆形#xff08;环形#xff09;排列的变体更是因其边界特殊性成为面试与竞赛中的高频考点。本文将从线性石子合并入手#xff0c;拆解环形问题的核心难点#xff0c;详解“断环成链”的解题套路…在算法领域石子合并问题是动态规划的经典应用场景而圆形环形排列的变体更是因其边界特殊性成为面试与竞赛中的高频考点。本文将从线性石子合并入手拆解环形问题的核心难点详解“断环成链”的解题套路并附上完整代码实现帮你彻底掌握这一题型。一、问题描述有N堆石子以圆形操场为载体首尾相连排列每堆石子有固定数量。规定每次只能合并相邻的两堆石子合并后新堆的石子数即为该次合并的得分。要求通过合理规划合并顺序计算出将所有石子合并成一堆的最小得分和最大得分 。二、核心思路从线性到环形的转化1. 线性石子合并动态规划基础在解决环形问题前先回顾更简单的线性石子合并石子排成一排其核心逻辑是动态规划的区间DP思想- 状态定义设 dp[i][j] 表示合并第i堆到第j堆石子的最小或最大得分。- 状态转移合并区间 [i,j] 时必然存在一个分割点ki≤kj先合并 [i,k] 和 [k1,j] 再合并这两部分。转移方程为plaintextdp[i][j] min/max(dp[i][k] dp[k1][j] sum(i,j))其中 sum(i,j) 是区间 [i,j] 的石子总数可通过前缀和数组 pre 快速计算 sum(i,j) pre[j] - pre[i-1] 。- 遍历顺序必须按区间长度L从2到N枚举再枚举起点i计算终点jiL-1确保计算大区间时小区间已完成更新 。2. 环形问题的关键断环成链环形与线性的核心区别是首尾相邻合并时需考虑“第N堆与第1堆相邻”的特殊情况。解决思路是“断环成链”——将环形数组展开为长度为2N的线性数组其中前N个元素为原数组后N个元素重复原数组内容 。例如原数组 [a1,a2,a3] 展开后为 [a1,a2,a3,a1,a2,a3] 。此时任意长度为N的连续子区间如 [a3,a1,a2] 都对应环形的一种“断环”方式。我们只需在展开后的数组上计算所有长度为N的区间的最小/最大得分即可得到原环形问题的答案。三、完整实现步骤1. 数据预处理- 读取N堆石子的数量存储在数组 a 中下标从1开始。- 构建前缀和数组 pre 其中 pre[0]0 pre[i] pre[i-1] a[(i-1)%N 1] 适配展开后的数组。2. 动态规划数组初始化- 定义 min_dp[i][j] 存储区间 [i,j] 的最小合并得分 max_dp[i][j] 存储最大得分。- 初始化当区间长度为1时ij合并得分为0无需合并即 min_dp[i][i] max_dp[i][i] 0 。3. 区间DP遍历- 枚举区间长度L从2到N代表当前合并的堆数。- 枚举起点i从1到2N-L1确保终点jiL-1不超过2N。- 计算终点j i L - 1遍历分割点k从i到j-1更新状态转移方程plaintextsum pre[j] - pre[i-1]min_dp[i][j] min(min_dp[i][j], min_dp[i][k] min_dp[k1][j] sum)max_dp[i][j] max(max_dp[i][j], max_dp[i][k] max_dp[k1][j] sum)4. 计算最终结果- 遍历所有长度为N的区间起点i从1到N最终答案为- 最小得分 min(min_dp[i][iN-1]) i1~N- 最大得分 max(max_dp[i][iN-1]) i1~N四、C完整代码cpp#include bits/stdc.husing namespace std;const int INF 0x3f3f3f3f;const int MAXN 410; // 2*200适配N≤200的情况int main() {int n;cin n;int a[MAXN], pre[MAXN] {0};for (int i 1; i n; i) {cin a[i];a[i n] a[i]; // 断环成链展开为2n长度}// 计算前缀和for (int i 1; i 2 * n; i) {pre[i] pre[i - 1] a[i];}int min_dp[MAXN][MAXN], max_dp[MAXN][MAXN];memset(min_dp, INF, sizeof(min_dp));memset(max_dp, 0, sizeof(max_dp));// 初始化单个区间for (int i 1; i 2 * n; i) {min_dp[i][i] 0;max_dp[i][i] 0;}// 枚举区间长度L合并的堆数for (int L 2; L n; L) {// 枚举起点ifor (int i 1; i L - 1 2 * n; i) {int j i L - 1; // 终点// 枚举分割点kfor (int k i; k j; k) {int sum pre[j] - pre[i - 1];min_dp[i][j] min(min_dp[i][j], min_dp[i][k] min_dp[k 1][j] sum);max_dp[i][j] max(max_dp[i][j], max_dp[i][k] max_dp[k 1][j] sum);}}}// 查找所有长度为n的区间的最小/最大值int min_res INF, max_res 0;for (int i 1; i n; i) {min_res min(min_res, min_dp[i][i n - 1]);max_res max(max_res, max_dp[i][i n - 1]);}cout 最小得分 min_res endl;cout 最大得分 max_res endl;return 0;}五、复杂度分析与注意事项- 时间复杂度O(N³)其中N为石子堆数。三层循环分别对应区间长度、起点、分割点在N≤200时效率足够。- 空间复杂度O(N²)用于存储动态规划数组和前缀和数组。- 注意事项展开数组时需确保长度为2N避免边界越界初始化 min_dp 时需设为无穷大 max_dp 设为0保证状态转移的正确性。六、总结环形石子合并的核心是“断环成链”将环形问题转化为熟悉的线性区间DP问题再通过前缀和优化区间和计算最终高效求解最小和最大得分。这一“转化思想”不仅适用于石子合并还可迁移到环形排列的其他动态规划问题中如环形最大子数组和。建议结合线性石子合并问题对比练习重点体会“断环”的合理性与区间DP的遍历顺序逻辑。如果需要针对特定N值的测试用例调试或想了解优化O(N³)复杂度的四边形不等式技巧欢迎留言交流