石子合并

野性酷女 2022-08-11 08:58 159阅读 0赞

经典动态规划，本题的思想就是将n个石子合并的大问题逐渐从2个小石子合并的小问题逐渐推出

<pre name="code" class="cpp">#include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N=205;
    const int inf=0x3f3f3f3f;
    int sum[N],stone[N],dp[N][N];
    
    int min(int x,int y)
    {
    	return x>y?y:x;
    }
    void initi(int n)
    {
    	for(int i=0;i<=n;i++)
    		dp[i][i]=0;
    }
    int get_min(int n)
    {
    	initi(n);
    	for(int gap=1;gap<n;gap++)
    	{
    		for(int i=1;i<=n-gap;i++)//先从小问题，逐渐推出大问题
    		{
    			int j=i+gap;//显然gap表示i到j距离的大小

dp[i][j]=inf;
    			int tmp=sum[j]-sum[i-1];//i 到j的石子的重量之和
    			for(int k=i;k<j;k++)
    				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+tmp);//将dp【i,j】更新为i到j合并的最小值
    		}
    	}
    return dp[1][n];
    }
    int main()
    {
    	int T,n;
    	// scanf("%d",&T);
    	while(scanf("%d",&n)==1&&n)
    	{
    		sum[0]=0;
    		for(int i=1;i<=n;i++)
    			{
    				scanf("%d",stone+i);
    				sum[i]=sum[i-1]+stone[i];//初始化前I个石子重量之和
    			}
    		printf("%d\n",get_min(n));
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关区间DP | 2：环上的合并石子 —— 例题：合并石子（环形）

本文是在[区间DP | 1：矩阵链乘问题（含优化） —— 例题：矩阵链乘、合并石子][DP _ 1_ _] 上的升级（建议先看链接文章）。从链到环的改变，但本质还是区间dp问题

傷城~/ 2023年07月17日 07:28/ 0 赞/ 1 阅读

相关石子合并问题（JAVA版）

一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆

- 日理万妓/ 2023年06月08日 06:17/ 0 赞/ 4 阅读

相关石子合并问题（区间dp）

include <iostream> using namespace std; define ios ios_base::sync_with_stdio

分手后的思念是犯贱/ 2022年10月11日 00:59/ 0 赞/ 170 阅读

相关石子合并问题（区间dp）

石子合并问题是最经典的DP问题。首先它有如下3种题型： (1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的

叁歲伎倆/ 2022年09月28日 05:53/ 0 赞/ 174 阅读

相关 282 石子合并（区间dp）

1. 问题描述：设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两

朱雀/ 2022年09月12日 12:49/ 0 赞/ 200 阅读

相关 dp 石子合并问题

石子合并问题：有n(N<100)堆石子，价值分别为a0,a1......a(n-1),每次将其中的相邻的两堆合并，合并的代价为两堆石子的价值和,合并后用合并之后的一堆石子代

￡神魔★判官ぃ/ 2022年08月18日 00:58/ 0 赞/ 192 阅读

相关石子合并

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

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

相关石子合并问题

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

傷城~/ 2022年08月02日 07:19/ 0 赞/ 193 阅读

相关 ACM DP 石子合并问题

滴，集训第二十一天打卡。可能是对组队不太满意，都不大高兴做新的训练... 所以最近一直在磨DP，翻一下博客，发现最近都是DP啊... 这个石子合并的，我做的训练数据n是

小灰灰/ 2022年06月10日 01:17/ 0 赞/ 180 阅读

相关【p1880】石子合并

[https://www.luogu.org/problem/show?pid=1880][https_www.luogu.org_problem_show_pid_1880]

忘是亡心i/ 2022年06月06日 01:55/ 0 赞/ 137 阅读