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

太过爱你忘了你带给我的痛 2022-06-11 08:14 378阅读 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 条评论，378人围观）

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

相关阅读

相关 codevs1048 石子归并动态规划dp

include<iostream> include<cstring> using namespace std; int n,a[1000]={0

今天药忘吃喽~/ 2024年02月17日 19:26/ 0 赞/ 26 阅读

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

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

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

相关石子合并

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

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

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

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

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

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

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

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

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

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

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

相关方格取数（动态规划经典题）

描述设有N\N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：< p=""> ![1444824807.png

墨蓝/ 2022年06月10日 05:18/ 0 赞/ 229 阅读

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

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

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

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

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

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

相关经典算法：动态规划

链接1：[https://blog.csdn.net/zw6161080123/article/details/80639932][https_blog.csdn.net_zw

灰太狼/ 2021年12月15日 01:51/ 0 赞/ 358 阅读