合并石子（动态规划经典题）

太过爱你忘了你带给我的痛 2022-06-11 08:14 402阅读 0赞

步骤：

1. 设状态：f\[i\]\[j\]表示从第i堆合并到第j堆，合并成一堆的最小得分

2. 初始状态：f\[i\]\[i\]=0;

最终状态：f\[1\]\[n\];//从第1堆合并到第n堆的最小得分

3.状态转移方程：f\[i\]\[j\]=max(f\[i\]\[j\],f\[i\]\[k\]+f\[k+1\]\[j\]+s\[j\]-s\[i-1\]);//s\[i\]表示前i堆石头数量总和

/*
    7
    13
    7
    8
    16
    21
    4
    18
    */ 
    #include<iostream>
    #include<cstring>
    using namespace std;
    int f[101][101];//f[i][j]表示从第i堆石头合并到第j堆石头最小得分（从问题出发，缩小规模） 
    int s[101];//s[i]表示前i堆石头的数量总和 
    int main()
    {
    	int n,x; 
    	cin>>n;//有n堆石头
    	for(int i=1;i<=n;i++)
    	{
    		cin>>x;//第i堆石头的个数
    		s[i]=s[i-1]+x;//前i堆石头的数量总和 
    	} 
    	memset(f,127/3,sizeof(f));//将f[][]初始化为很大的一个值
    	for(int i=1;i<=n;i++) f[i][i]=0;//初始状态
    	for(int i=n-1;i>=1;i--)//从第i堆到第j堆，j>i,由后往前进行合并 
    	{
    		for(int j=i+1;j<=n;j++)
    		{
    			for(int k=i;k<=j-1;k++)//k表示最后一次合并时是哪两堆进行合并，两堆：f[i][k],f[k+1][j](i<=k<=j-1) 
    			{
    				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);//s[j]-s[i-1]表示最后一次合并的得分 
    			}
    		}
    	} 
    	cout<<f[1][n]<<endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，402人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划 | 区间dp No.2】AcWing 1068.环形石子合并

【算法|动态规划 | 区间dp No.2】AcWing 1068.环形石子合并

Myth丶恋晨/ 2024年04月27日 07:02/ 0 赞/ 63 阅读

相关【算法|动态规划 | 区间dp No.1】AcWing 282. 石子合并

【算法|动态规划 | 区间dp No.1】AcWing 282. 石子合并

淩亂°似流年/ 2024年04月27日 07:02/ 0 赞/ 72 阅读

相关租用游艇问题石子合并问题动态规划实验

实验名称：动态规划一、实验预习 1、实验目的 1. 理解并掌握动态规划方法的设计思想； 2. 提高应用动态规划方法解决问题和设计算法的能力； 3. 通过编程实现

以你之姓@/ 2023年09月29日 15:34/ 0 赞/ 18 阅读

相关算法设计与分析——动态规划——石子合并问题

1.石子合并问题在一个圆形操场的四周摆放着n堆石子。现要将石子有序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。设计一个

叁歲伎倆/ 2022年10月14日 15:56/ 0 赞/ 219 阅读

相关石子合并

经典动态规划，本题的思想就是将n个石子合并的大问题逐渐从2个小石子合并的小问题逐渐推出 <pre name="code" class="cpp">inclu

野性酷女/ 2022年08月11日 08:58/ 0 赞/ 173 阅读

相关乘积最大（动态规划经典题）

描述今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的

本是古典何须时尚/ 2022年06月11日 08:16/ 0 赞/ 249 阅读

相关合并石子（动态规划经典题）

步骤： 1. 设状态：f\[i\]\[j\]表示从第i堆合并到第j堆，合并成一堆的最小得分 2. 初始状态：f\[i\]\[i\]=0; 最终状态：f\[1\]\[n\]

太过爱你忘了你带给我的痛/ 2022年06月11日 08:14/ 0 赞/ 403 阅读

相关复制书稿（动态规划经典题）

Problem Description 现在要把m本有顺序的书分给k个人复制(抄写)，每一个人的抄写速度都一样，一本书不允许给两个(或以上)的人抄写，分给每一个人的书，必须

水深无声/ 2022年06月10日 10:06/ 0 赞/ 220 阅读

相关动态规划之石子合并问题

\include <iostream> using namespace std; \define LEN 1024 \define MAXDATA 200000 i

Bertha 。/ 2022年04月22日 02:14/ 0 赞/ 225 阅读

相关详解动态规划石子合并问题(直线型, 环形)

题目描述在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，合并的花费为这相邻两堆之和试设计出1个算法,计算出将

朴灿烈づ我的快乐病毒、/ 2022年02月22日 21:14/ 0 赞/ 268 阅读