精华内容
下载资源
问答
  • 动态规划之合并石子

    千次阅读 多人点赞 2020-08-17 21:40:43
    动态规划——合并石子(C语言解) 第一次接触到动态规划是在斐波那契数列,那个时候还不知道动态规划的概念,由于数据量较小,直接用for循环就通过了,直到遇到了”合并石子“这道题目,百度过很多的文章都没看懂,...

    动态规划——合并石子(C语言解)

    第一次接触到动态规划是在斐波那契数列,那个时候还不知道动态规划的概念,由于数据量较小,直接用for循环就通过了,直到遇到了”合并石子“这道题目,百度过很多的文章都没看懂,大佬们都讲得太抽象了,一上来就是状态改变方程,算法小白一脸懵逼。经过一段时间的理解我终于搞懂了这道题目,下面说一说我的解法(可能不是最佳解法),希望能帮到大家。

    动态规划的概念

    首先我们要搞懂什么是动态规划。我觉得动态规划就是把一个大问题分解为多个小问题,每个小问题的决策都会影响到下一个小问题的决策。(下一个小问题的决策就是由上一个小问题的决策而产生的。)一个状态经过一个决策变成了另外一个状态,这个过程就是状态转移,用来描述状态转移的方程就是状态转移方程。

    题目和思路

    在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。请设计一个程序,计算出将N堆石子合并成一堆的最小得分。

    我们首先来分析一个比较简单的问题,现在一共有三堆石头,每堆石子的数量分别是3,4,11。求合并成一堆石头的最小得分。
    对于这个问题,只有两种选择:
    前两堆石头合并再和第三堆石头合并。
    3+4=7 ——> 7 石堆变为(7, 11)
    7+11=18——>18 石堆变为(18)
    cost=7+18=25
    后两堆石头合并再和第一堆石头合并。
    4+11=15——>15 石堆变为(3,15)
    3+15=18——>18 石堆变为(18)
    cost=15+18=33

    易看出先合并前两堆的石子的花费比较小,不同的合并方式会造成不同的得分。同时可以发现这两种方法最后一次的得分就是石头的总数。
    现在我们用一个数组arr[]按顺序保存每个位置的石头数量。
    arr[]={3,4,11}

    二维数组sum[i][j]表示第i堆石头到第j堆石头的总和
    sum[0][1]=3+4=7;
    sum[1][2]=4+11=15;
    sum[0][2]=3+4+11=18;

    最后用一个二维数组dp[i][j]表示从第i堆到第j堆石头合并的最小分数。
    1)每堆石头跟自己合并的分数都是0。
    dp[0][0]=dp[1][1]=dp[2][2]=0
    2)相邻两堆石头的最小合并分数只有一种可能。
    dp[0][1]=3+4=7, dp[1][2]=4+11=15
    3)剩下的就是不相邻石头的合并最小花费。
    设一个k∈[i,j];
    dp[i][j]=dp[i][k]+dp[k][j]+sum[i][j];
    那么从i到j的所有花费都可以表示出来了,取一个使得dp[i][j]最小的值。
    我们用表格来表示出从i到j的费用最小值。(对于C来说一般是序号从0开始)
    在这里插入图片描述
    dp[1][3]=min(dp[1][1]+dp[2][3] , dp[1][2]+dp[3][3])+sum[1][3];
    dp[2][4]=min(dp[2][3]+dp[4][4] , dp[2][2]+dp[3][4])+sum[2][4];
    dp[1][4]=min(dp[1][1]+dp[2][4],dp[1][2]+dp[3][4],dp[1][3]+dp[4][4])+sum[1][4];
    我们最终的目的是求出dp[1][4],那我们就要先求出dp[1][3]和dp[2][4],从图像上我们要求最右上角的值,就是沿着副对角线一步步往上求。
    在这里插入图片描述
    思路就是这样了,下面是代码。

    具体代码

    #include <stdio.h>
    int main()
    {
        int n,i,j,t,a,b;
        int arr[100];     
        int sum[100][100],dp[100][100];
        scanf("%d",&n);
        for (i=0; i<n; i++) {
            scanf("%d",&arr[i]);         //储存初始的每个位置的石头数量
        }
        for (i=0; i<n; i++) {
            for (j=i; j<n; j++) {
                if (i==j) {
                    sum[i][j]=arr[i];     
                }
                else
                    sum[i][j]=sum[i][j-1]+arr[j];
            }  
        }                                //计算从i到j的石头总和
        for (i=0; i<n; i++) {
            dp[i][i]=0;
            if (i<n-1) {
                dp[i][i+1]=arr[i]+arr[i+1];  
            }
        }                     //把同一堆石头和相邻两堆石头合并的值计算
        for (t=2; t<=n; t++) {
            for (i=0; i<n-t; i++) {
                a=dp[i][i+t-1]+sum[i][i+t];
                b=dp[i][i]+dp[i+1][i+t]+sum[i][i+t];
                for (j=1; j<t-1; j++) {
                    if (b>dp[i][i+j]+dp[i+j+1][i+t]+sum[i][i+t]) {
                        b=dp[i][i+j]+dp[i+j+1][i+t]+sum[i][i+t];
                    }
                }
                if (a<=b) {
                    dp[i][i+t]=a;
                }
                else
                    dp[i][i+t]=b;
            }
        }            //按照表格从副对角线往依次计算的方法,最后求出右上角的值
        printf("%d",dp[0][n-1]);
        return 0;
    }
    

    有更好的方法欢迎交流~~
    想学动态规划的可以看看这篇文章:告别动态规划,连刷40道动规算法题,我总结了动规的套路。

    展开全文
  • 合并石子

    2019-02-27 16:30:31
    设 Min [i][j] 代表从第 i 堆石子到第 j 堆石子合并的最小花费, Min [i][k] 代表从第 i 堆石子到第 k 堆石子合并的最小花费,Min[k+1][j] 代表从第 k+1 堆石子到第 j 堆石子合并的最小花费, w ( i , j )代表从 i 堆到...

    分析
    ( 1 )建立最优值递归式
    设 Min [i][j] 代表从第 i 堆石子到第 j 堆石子合并的最小花费, Min [i][k] 代表从第 i 堆石子到第 k 堆石子合并的最小花费,Min[k+1][j] 代表从第 k+1 堆石子到第 j 堆石子合并的最小花费, w ( i , j )代表从 i 堆到 j 堆的石子数量之和。列出递归式:
    Min [ i ][ j ] = 0 (i = j)
    Min [ i ][ j ] = min ( Min [ i ][ k ] + Min [ k + 1][ j ] + w ( i , j )) , i < j( i ≤ k < j)
    Max [i][j] 代表从第 i 堆石子到第 j 堆石子合并的最大花费,Max [i][k] 代表从第 i 堆
    石子到第 k 堆石子合并的最大花费,Max [k+1][j] 代表从第 k+1 堆石子到第 j 堆石子合并的最大花费, w ( i , j )代表从 i 堆到 j 堆的石子数量之和。列出递归式:

    Max [ i ][ j ] = 0 (i = j)
    Max [ i ][ j ] =max( Max [ i ][ k ] + Max [ k + 1][ j ] + w ( i , j )) , i < j ( i ≤ k < j)
    二维数组 Min [i][j] 、Max [i][j] 来记录第 i 堆到第 j 堆 a i , a i+1 ,…, a i 堆石子合并的最小花费和最大花费。
    ( 2 )初始化
    输入石子的堆数 n ,然后依次输入各堆石子的数量存储在 a[i] 中,令 Min [i][i]=0 ,
    Max [i][i]=0 , sum[0]=0 ,计算 sum[i] ,其中 i= 1 , 2 , 3 ,…, n 。
    ( 3 )循环阶段
    • 按照递归式计算 2 堆石子合并 {a i , a i+1 } 的最小花费和最大花费, i=1 , 2 , 3 ,…, n−1 。
    • 按照递归式计算 3 堆石子合并 {a i , a i+1 , a i+2 } 的最小花费和最大花费, i=1 , 2 , 3 ,…,n−2 。

    展开全文
  • 试题 算法提高 合并石子 资源限制 时间限制:2.0s 内存限制:256.0MB 问题描述  在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数...

    试题 算法提高 合并石子


    时间限制:2.0s 内存限制:256.0MB
    问题描述
      在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
    输入格式
      输入第一行包含一个整数n,表示石子的堆数。
      接下来一行,包含n个整数,按顺序给出每堆石子的大小 。
    输出格式
      输出一个整数,表示合并的最小花费。
    样例输入
    5
    1 2 3 4 5
    样例输出
    33
    数据规模和约定
      1<=n<=1000, 每堆石子至少1颗,最多10000颗。
    思路:
    题目意思就是在n堆石子中不断的合并相邻的石头直到合并成1堆,然后叫我们算出最小花费。题目的花费情况是合并的费用为两堆石子的总数,意思就是当我们合并1和2 那么花费就是3 合并的3和之前的3合并花费总和就是3+3+3=9还要加之前的花费。
    那我们可以分解此题,假设我们有1个石头那花费是0,2个石头那么就是他们的总和,3个石头那我们怎么划分呢,我们可以把他分解出来 :
    第一种
    我们可以将前面(第1堆和第2堆合并的花费值+第3堆花费值)+他们3个石头的数量=总花费值 (因为花费值并没有把本身的石头值加到花费里面。)
    第二种
    (第2堆和第3堆合并的花费值+第1堆花费值)+他们3个石头的数量=总花费值 依次类推…
    那我们从上面可以知道可以用动态规划的方式完成。
    我们可以先把第1堆到n的每个区域储存起来我存储到了ad列表中。我们在建立一个dp[j][j1]表示j-j1之间的最小花费。
    我们建立2层for循环第一层表示长度 第二层表示当前开头的堆 那 堆尾=开头+长度
    从上述可知我们需要把这n堆石子的可能性列出来。那我们就建立一个for 从j-j1 因为我们遍历的是当前的n堆的可能性,那么dp[j][k] 表示的是前面j-k的堆 后面那么就表示 dp[k+1][j1], 这就是我们合并所花费的值。并没有把本身的石头值加到花费里面。所以还要加ad[j1]-ad[j-1].
    那么我们的转移方程就是:dp[j][k]+dp[k+1][j1]+ad[j1]-ad[j-1]
    然后在和本身的数比较最小值:
    min(dp[j][j1],dp[j][k]+dp[k+1][j1]+ad[j1]-ad[j-1]) 注意我是从1开始的。
    程序:

    n=int(input())
    a=list(map(int,input().split()))
    dp=[[999999999999 for i1 in range(n+5)] for i in range(n+5)]  #dp初始化
    ad=[ 0 for i in range(1005)]
    for i in range(1,n+1):
        ad[i]=ad[i-1]+a[i-1] #把第0堆到i的每个区域储存起来
        dp[i][i]=0   #1堆最小花费为0
    for i in range(1,n+1):   #表示j+i之间的堆  可以说是当前的长度。
        for j in range(1,n-i+1):  #当前开头堆
            j1=i+j  #结尾堆
            for k in range(j,j1+1):  #把这n堆石子的可能性列出来
                dp[j][j1]=min(dp[j][j1],dp[j][k]+dp[k+1][j1]+ad[j1]-ad[j-1])
    print(dp[1][n])
    

    禁止转载。仅用于自己学习。对程序错误不负责。

    展开全文
  • 算法提高 合并石子

    2019-09-25 01:32:54
    算法提高 合并石子 时间限制:2.0s 内存限制:256.0MB 问题描述  在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数。...

      

      算法提高 合并石子  
    时间限制:2.0s   内存限制:256.0MB
     
    问题描述
      在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
    输入格式
      输入第一行包含一个整数n,表示石子的堆数。
      接下来一行,包含n个整数,按顺序给出每堆石子的大小 。
    输出格式
      输出一个整数,表示合并的最小花费。
    样例输入
    5
    1 2 3 4 5
    样例输出
    33
    数据规模和约定
      1<=n<=1000, 每堆石子至少1颗,最多10000颗。
     
    时间超限:数据通过80%数据
    /*
        long long最大值和最小值都是19位数 
    */
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    using namespace std;
    long long n,a[1010],dp[1010][1010],sum[1010];
    int main(void){
        cin >> n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dp[i][j] = 100000000000000000;    
        //memset(dp,1,sizeof(dp)); 
        for(int i=1;i<=n;i++){
            cin >> a[i];
            dp[i][i] = 0;
            sum[i] = sum[i-1] + a[i]; //初始化sum[] 
        }
        if(n == 1){
            cout << 0;
            return 0; 
        }
        for(int len=2;len<=n;len++){
            for(int i=1;i<=n-len+1;i++){
                int j=i+len-1;
                for(int k=i;k<j;k++){
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
                }
            }
        }
        cout << dp[1][n];
        return 0;
    }

     

     

    转载于:https://www.cnblogs.com/zuimeiyujianni/p/8504386.html

    展开全文
  • #区间dp之合并石子(经典例题) 石子合并 题目大概意思是 n 堆石子摆成一个圆形,每次只能用相邻的两堆石子进行合并,并且得分为这两堆石子的重量总和,问你你可取得的最大分数和最小分数是多少? 样例输入 4 4 5 9 ...
  • //优先队列方法 #include <iostream> #include <algorithm> #define maxn 100005 using namespace std; int main () { int n; long long ans = 0; int a[maxn],b[maxn]={0};... ...
  • 合并石子(三种方法)

    千次阅读 多人点赞 2018-12-08 08:26:47
    合并石子 题目 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。请设计一个程序,计算出将N堆石子合并成一...
  • 找题目?故作深沉的传送门 ...按照贪心(每次都合并最小值)算一算,结果应该是248本来画了图,太丑不敢放 但是,样例输出是239,所以贪心不可行 接下来就剩动规一种选择了 状态转移方程: f[i][j]=min(f[i][j]...
  • 试题 算法提高 合并石子 资源限制 时间限制:2.0s 内存限制:256.0MB 问题描述  在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数...
  • 1274:【例9.18】合并石子 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 5188 通过数: 3293 【题目描述】 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并...
  • 设序列是stone[],从左...= stone[k+1]的k,找到后合并stone[k]和stone[k-1],再从当前位置开始向左找最大的j,使其满足stone[j] &gt; stone[k]+stone[k-1],插到j的后面就行。一直重复,直到只剩下一堆石子就...
  • 试题 算法提高 合并石子 资源限制 时间限制:2.0s 内存限制:256.0MB 问题描述  在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数...
  •  在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并合并后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。 输入格式  输入第一行包含一个整数n,...
  • 本文是在区间DP | 1:矩阵链乘问题(含优化) —— 例题:矩阵链乘、合并石子上的升级(建议先看链接文章)。从链到环的改变,但本质还是区间dp问题,将环的区间任然解析成链即可。 环上的合并石子问题:环形排列...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,470
精华内容 2,988
关键字:

合并石子