七台河网站制作咨询公司网站模板

七台河网站制作,咨询公司网站模板,企业网站优化解决方案,商务网站开发的基本流程经典问题描述#xff1a;有 n 堆石子排成一排#xff0c;第 i 堆有 ai 个石子。 每次只能合并相邻的两堆#xff0c;合并代价等于这两堆石子的总数。 合并后形成一堆新石子。 问#xff1a;把所有石子合并成一堆的最小总代价。输入3(n的大小)8 5 8输出34解释#xff1a;首…经典问题描述有 n 堆石子排成一排第 i 堆有 ai 个石子。每次只能合并相邻的两堆合并代价等于这两堆石子的总数。合并后形成一堆新石子。问把所有石子合并成一堆的最小总代价。输入3(n的大小)8 5 8输出34解释首先合并8-5成13代价是13. 合并后石子为13 8.然后合并13-8代价是21.所以总代价为34贪心or动态规划在石子合并里最自然的贪心直觉只有这一种每一步都合并当前代价最小的相邻两堆也就是每次找 a[i] a[i1] 最小的一对先合它这个策略非常“像 Huffman”所以特别容易误入。⚠️ 问题就出在石子合并中一次合并的结果会被“反复收费”所以当前的最小代码并不是全局的最小代价。这就是贪心失效的根本原因贪心反例石子堆 4 3 3 4贪心做法每次合最小相邻对1️⃣ 合并中间的3 3 6代价 6现在变成4 6 42️⃣ 合并4 6 10或 64代价 10现在变成10 43️⃣ 合并10 4 14代价 14 总代价6 10 14 30最优做法非贪心1️⃣ 先合左边4 3 7代价 77 3 42️⃣ 再合右边3 4 7代价 77 73️⃣ 最后合并7 7 14代价 14 总代价7 7 14 28这是一个「区间 DP」问题记住一句判断口诀“对象是连续区间决策是选断点代价和区间整体有关”→ 基本就是区间 DP我们逐条对照石子合并状态的本质是什么最终不是关心“某一步怎么合”而是关心某一段连续石子合并成一堆最少要花多少钱这句话本身就已经是一个区间[l ........ r]所以状态一定是dp[l][r] 把第 l 堆到第 r 堆合并成一堆的最小代价⚠️ 注意不是过程是“已经合并完成”的最优结果状态转移是怎么发生的不管你前面怎么合最后一步一定是把某两堆「已经合并好的大堆」合成一堆而这两堆必然形如[l .... k] [k1 .... r][l..k]和[k1..r]各自已经合成一堆合并它们的代价 区间总石子数设前缀和sum[i] a1 a2 ... ai那么cost(l, r) sum[r] - sum[l-1]所以状态转移就只能是dp[l][r] min over k∈[l, r-1] ( dp[l][k] dp[k1][r] cost(l, r) )边界条件一个堆需要合并吗dp[i][i] 0不需要任何代价C代码实现int sum(int prefix[], int l, int r) { return prefix[r] - prefix[l - 1]; } int main() { int n; cin n; int a[107], prefix[107] { 0 }; //我这里下标是从1开始的 for (int i 1; i n; i) { cin a[i]; } //prefix[i]是从[1,i]的和 for (int i 1; i n; i) { prefix[i] prefix[i - 1] a[i]; } //dp表示把区间 [l, r] 合并成一堆的最小代价 long long dp[107][107]; //单根不用合并 for (int i 1; i n; i) dp[i][i] 0; //枚举合并区间长度 for (int len 2; len n; len) { //枚举开始位置 for (int l 1; l len - 1 n; l) { //区间是[l,llen-1],长度就是len int r l len - 1; dp[l][r] LLONG_MAX; //所谓合并可以这么理解 //如果[l,k]和[k1,r]已经合并完了那么再合并的代价就是sum(l,k)sum(k1,r)即sum(l,r) //然后[l,k]和[k1,r]也有合并的代价所以[l,k]和[k1,r]的合并代价就是dp[l][k]dp[k1][r]sum(l,r) //我们枚举所有k属于[l,r)这样就能找到dp[l][r]的最小合并代价 for (int k l; k r; k) { dp[l][r] fmin(dp[l][r], dp[l][k]dp[k1][r]sum(prefix,l,r)); } } } cout dp[1][n]; }