做网站用什么软件免费郑州网站科技

做网站用什么软件免费,郑州网站科技,竞价交易,伪原创php网站镜像同步程序在算法设计中#xff0c;圆形石子合并问题是经典的动态规划应用场景之一。本文将详细讲解该问题的解法#xff0c;并用 C 实现 3 种不同算法#xff0c;最后对比它们的优劣。 一、问题描述 在圆形操场周围有 n 堆石子#xff0c;每次只能合并相邻的 2 堆#xff0c;合并…在算法设计中圆形石子合并问题是经典的动态规划应用场景之一。本文将详细讲解该问题的解法并用 C 实现 3 种不同算法最后对比它们的优劣。一、问题描述在圆形操场周围有n堆石子每次只能合并相邻的 2 堆合并得分是新堆的石子数。求将所有石子合并为 1 堆的最小得分和最大得分。二、算法 1基础动态规划环形转线性思路圆形结构可通过复制数组转化为线性结构长度为2n再用区间 DP 求解定义dp_min[i][j]合并区间[i,j]的最小得分定义dp_max[i][j]合并区间[i,j]的最大得分状态转移dp_min[i][j]min(dp_min[i][k]dp_min[k1][j])sum(i,j)(i≤kj)dp_max[i][j]max(dp_max[i][k]dp_max[k1][j])sum(i,j)(i≤kj)sum(i,j)是区间[i,j]的石子总数用前缀和快速计算C 代码#include iostream #include vector #include climits using namespace std; // 计算前缀和 vectorint getPrefixSum(const vectorint arr) { vectorint pre(arr.size() 1, 0); for (int i 0; i arr.size(); i) { pre[i1] pre[i] arr[i]; } return pre; } // 区间[i,j]的和基于前缀和 int getSum(const vectorint pre, int i, int j) { return pre[j1] - pre[i]; } pairint, int stoneMergeDP(vectorint stones) { int n stones.size(); if (n 1) return {0, 0}; // 环形转线性复制数组 vectorint arr stones; arr.insert(arr.end(), stones.begin(), stones.end()); vectorint pre getPrefixSum(arr); int len 2 * n; vectorvectorint dp_min(len, vectorint(len, 0)); vectorvectorint dp_max(len, vectorint(len, 0)); // 枚举区间长度从2到n for (int l 2; l n; l) { for (int i 0; i l len; i) { int j i l - 1; dp_min[i][j] INT_MAX; dp_max[i][j] INT_MIN; // 枚举分割点 for (int k i; k j; k) { int sum getSum(pre, i, j); dp_min[i][j] min(dp_min[i][j], dp_min[i][k] dp_min[k1][j] sum); dp_max[i][j] max(dp_max[i][j], dp_max[i][k] dp_max[k1][j] sum); } } } // 遍历所有长度为n的区间取最小/最大值 int min_res INT_MAX, max_res INT_MIN; for (int i 0; i n; i) { min_res min(min_res, dp_min[i][i n - 1]); max_res max(max_res, dp_max[i][i n - 1]); } return {min_res, max_res}; } int main() { vectorint stones {4, 1, 2, 3}; // 测试用例 auto [min_score, max_score] stoneMergeDP(stones); cout 最小得分 min_score endl; cout 最大得分 max_score endl; return 0; }三、算法 2贪心算法仅适用于链形 特殊条件思路贪心算法仅在链形结构 石子数非递减 / 非递增时有效圆形结构不适用核心是最小得分每次合并最小的相邻两堆类似哈夫曼编码最大得分每次合并最大的相邻两堆C 代码链形场景#include iostream #include vector #include queue using namespace std; // 贪心求最小得分链形 int greedyMin(vectorint stones) { priority_queueint, vectorint, greaterint pq(stones.begin(), stones.end()); int res 0; while (pq.size() 1) { int a pq.top(); pq.pop(); int b pq.top(); pq.pop(); res a b; pq.push(a b); } return res; } // 贪心求最大得分链形 int greedyMax(vectorint stones) { priority_queueint pq(stones.begin(), stones.end()); int res 0; while (pq.size() 1) { int a pq.top(); pq.pop(); int b pq.top(); pq.pop(); res a b; pq.push(a b); } return res; } int main() { vectorint stones {4, 1, 2, 3}; // 链形测试用例 cout 链形最小得分贪心 greedyMin(stones) endl; cout 链形最大得分贪心 greedyMax(stones) endl; return 0; }四、算法 3记忆化搜索递归 缓存思路基于基础 DP 的递归实现用记忆化缓存避免重复计算逻辑与基础 DP 一致但代码更简洁。C 代码#include iostream #include vector #include climits #include unordered_map using namespace std; vectorint pre; vectorvectorint memo_min, memo_max; int n; int dfs_min(int i, int j) { if (i j) return 0; if (memo_min[i][j] ! -1) return memo_min[i][j]; int res INT_MAX; for (int k i; k j; k) { int sum pre[j1] - pre[i]; res min(res, dfs_min(i, k) dfs_min(k1, j) sum); } return memo_min[i][j] res; } int dfs_max(int i, int j) { if (i j) return 0; if (memo_max[i][j] ! -1) return memo_max[i][j]; int res INT_MIN; for (int k i; k j; k) { int sum pre[j1] - pre[i]; res max(res, dfs_max(i, k) dfs_max(k1, j) sum); } return memo_max[i][j] res; } pairint, int stoneMergeMemo(vectorint stones) { n stones.size(); if (n 1) return {0, 0}; vectorint arr stones; arr.insert(arr.end(), stones.begin(), stones.end()); pre.resize(arr.size() 1, 0); for (int i 0; i arr.size(); i) { pre[i1] pre[i] arr[i]; } memo_min.assign(2*n, vectorint(2*n, -1)); memo_max.assign(2*n, vectorint(2*n, -1)); int min_res INT_MAX, max_res INT_MIN; for (int i 0; i n; i) { min_res min(min_res, dfs_min(i, i n - 1)); max_res max(max_res, dfs_max(i, i n - 1)); } return {min_res, max_res}; } int main() { vectorint stones {4, 1, 2, 3}; auto [min_score, max_score] stoneMergeMemo(stones); cout 最小得分记忆化 min_score endl; cout 最大得分记忆化 max_score endl; return 0; }五、算法优劣对比算法时间复杂度空间复杂度适用场景优点缺点基础 DPO(n3)O(n2)圆形 / 链形通用、结果准确时间复杂度高贪心算法O(nlogn)O(n)链形 特殊石子序列效率高圆形场景不适用、结果可能错误记忆化搜索O(n3)O(n2)圆形 / 链形代码简洁、逻辑直观递归栈深度限制、效率略低于迭代 DP六、总结圆形石子合并问题的最优解法是基础动态规划或记忆化搜索贪心算法仅适用于特殊场景。实际应用中若n较大如n100需优化 DP如四边形不等式优化时间复杂度可降为 O(n2)。