精华内容
下载资源
问答
  • 动态规划之环形石子合并问题
    2021-05-08 09:05:24

    题目

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

    测试用例:

    输入:

    4(石子的堆数)
    4 4 5 9(每一堆的石子数目)

    输出:

    43 54

     分析:

    我们知道链式的石子合并问题是相邻两堆之间可以合并,那么环形的和链式的区别就在于,环形的相当于是链式的头尾两堆也能合并

    那么,我们只要解决,如何在链式的基础上更换每次头和尾的问题即可,即环形的切割点

    n堆,有n个切割点,每次以区间长度为n的链式的进行求解。

    如果想n个切割点,每次长度为n,那么我们创建长度为2*n的数组,存放两次石子序列即可。

     

    最优子结构:

    和链式一样,合并两堆的代价最小

    即把当前的链式区间划分,左+右+合并左右 的代价达到最优即可

     int f[2 * n + 1][2 * n + 1];  //计算合并的最小值 f[i][j]表示i到j这个范围内合并的代价

     int g[2 * n + 1][2 * n + 1];  //计算合并的最大值 g[i][j]表示i到j这个范围内合并的代价

    #include <iostream>
    #include<cstring>
    using namespace std;
    //每次选取相邻的两堆合并 环形可以开2*n大小的数组,然后以n为区间进行求值
    //最优子问题:求解每小个区间(以k为分割点,左右还有合并左右的代价
    //这里计算合并左右的代价可以利用前缀和的方法 s[r]-s[l-1]
    #define Max 10005
    #define N 410
    int MAX(int a,int b){
        return a>b?a:b;
    }
    int MIN(int a,int b){
        return a<b?a:b;
    }
    int main() {
      int n;
      cin >> n;
      int a[2 * n + 1] = {};
      int f[2 * n + 1][2 * n + 1];  //计算合并的最小值 f[i][j]表示i到j这个范围内合并的代价
      int g[2 * n + 1][2 * n + 1];  //计算合并的最大值 g[i][j]表示i到j这个范围内合并的代价
       memset(f,Max,sizeof(f));
       memset(g,-Max,sizeof(g));
      int s[2 * n + 1] = {};
      for (int i = 1; i < n + 1; i++) {
        cin >> a[i];
        a[i + n] = a[i];
      }
      for (int i = 1; i <= 2 * n; i++) {  //计算前缀和
        s[i] = s[i - 1] + a[i];
        f[i][i]=0;
        g[i][i]=0;
      }
      //状态计算
      for (int len = 2; len <= n; len++) {  //区间划分
        for(int l=1;l+len-1<=2*n;l++){//左右
            int r=l+len-1;
            for(int k=l;k<r;k++){  //选择区间分割点 
              f[l][r]=MIN(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
              g[l][r]=MAX(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
        }
      }
    }
         int min=Max,max=-Max;
        for(int i=1;i<=n;i++){
            min=MIN(min,f[i][i+n-1]);
            max=MAX(max,g[i][i+n-1]);
        }
        cout<<min<<" "<<max<<endl;
    }

     

     

     

     

     

     

     

     

     

     

     

     

    更多相关内容
  • 1068. 环形石子合并

    2022-03-21 17:01:49
    将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 n 及每堆的石子数,并进行如下计算: ...

    将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。

    规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。

    请编写一个程序,读入堆数 n 及每堆的石子数,并进行如下计算:

    • 选择一种合并石子的方案,使得做 n−1 次合并得分总和最大。
    • 选择一种合并石子的方案,使得做 n−1 次合并得分总和最小。

    输入格式

    第一行包含整数 n,表示共有 n 堆石子。

    第二行包含 n 个整数,分别表示每堆石子的数量。

    输出格式

    输出共两行:

    第一行为合并得分总和最小值,

    第二行为合并得分总和最大值。

    数据范围

    1≤n≤200

    输入样例:

    4
    4 5 9 4
    

    输出样例:

    43
    54
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y6QJh19y-1647853285374)(1068.%20%E7%8E%AF%E5%BD%A2%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6.assets/35805_4dd2d434bc-%E7%8E%AF%E5%BD%A2%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6.jpg)]

    代码:

    /*
    在区间DP中,我们也常常省去 len 这一维的空间
    
    因为 r−l+1=len,也就保证了在已知 l 和 r 的情况下,不会出现状态定义重复的情况
    
    根据线性代数中方程的解的基本概念,我们就可以删掉 len 这一维不存在的约束
    
    但为了方便读者理解,以及介绍区间DP的阶段是如何划分的,我还是写了出来
    */
    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 410;
    int f[N][N], g[N][N];
    int w[N], s[N];
    int n;
    
    int main()
    {
        cin >> n;
        // 化环为链 n个点n-1条边 一定有两个点之间断开
        for (int i = 1; i <= n; i++)
        {
            cin >> w[i];
            w[i + n] = w[i];
        }
    
        memset(f, 0x3f, sizeof f);
        memset(g, -0x3f, sizeof g);
    
        for (int i = 1; i <= 2 * n; i++)
            f[i][i] = g[i][i] = 0;
    
        for (int i = 1; i <= 2 * n; i++)
            s[i] = s[i - 1] + w[i];
    
        for (int len = 2; len <= n; len++)
        {
            for (int i = 1; i + len - 1 <= 2 * n; i++)
            {
                int j = i + len - 1;
                for (int k = i; k < j; k++)
                {
                    f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                    g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
                }
            }
        }
    
        int minn = 0x3f3f3f3f, maxx = 0;
        for (int i = 1; i <= n; i++)
        {
            minn = min(minn, f[i][i + n - 1]);
            maxx = max(maxx, g[i][i + n - 1]);
        }
    
        cout << minn << endl
             << maxx << endl;
        return 0;
    }
    
    展开全文
  • 算法–环形石子合并问题设计过程 一.问题描述:在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一...

    算法–环形石子合并问题设计过程

    一.问题描述:在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。
    要求:对于任意给定的n堆石子,计算合并成一堆的最小得分和最大得分。
    二、问题及解决方案
    1)审题不清:题目要求的是将每两堆石子合并之后的数量与下一次合并之后的数量相加求得分,我们一开始理解成:相邻两堆石子合并后,用合并后的石子数量再与相邻石子合并相加求得分,如果这样想的话,最后的得分就是一个定值,即所有石子数之和,也就不存在最大得分和最小得分了。
    2)方法的使用:
    开始以为通过贪心算法可能很快解决问题,可是是行不通的。
    首先我们可以把这么堆石子看成一列,我们假如5堆的石子,其中石子数分别为7,6,5,7,100
    按照贪心法,合并的过程如下: 每次合并得分
    第一次合并 7 6 5 7 100 =11
    第二次合并 7 11 7 100=18
    第三次合并 18 7 100 =25
    第四次合并 25 100 =125
    总得分=11+18+25+125=179

    另一种合并方案 每次合并得分
    第一次合并 7 6 5 7 100 ->13
    第二次合并 13 5 7 100->12
    第三次合并 13 12 100 ->25
    第四次合并 25 100 ->125
    总得分=13+12+25+125=175
    由此可以看出,利用贪心法来做是错误的,贪心算法在子过程中得出的解只是局部最优,而不能保证使得全局的值最优。
    三、算法设计
    如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的。
    因此我们需要通过动态规划算法来求出最优解。
    在此我们假设有n堆石子,一字排开,合并相邻两堆的石子,每合并两堆石子得到一个分数,最终合并后总分数最少的。
    我们设m(i,j)定义为第i堆石子到第j堆石子合并后的最少总分数。a(i)为第i堆石子的石子数量。
    当合并的石子堆为1堆时,很明显m(i,i)的分数为0;
    当合并的石子堆为2堆时,m(i,i+1)的分数为a(i)+a(i+1);
    当合并的石子堆为3堆时,m(i,i+2)的分数为MIN((m(i,i)+m(i+1,i+2)+sum(i,i+2)),(m(i,i+1)+m(i+2,i+2)+sum(i,i+2));
    当合并的石子堆为4堆时…

    (1)求最小得分相应的代码如下:
    int MatrixChain_min(int p[N],int n)//p[N]石子数,n石子堆数
    {
    int m[N][N]; //定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目(石子积分)

    int min=0;                                                     
       for(int g = 1;g<=n;g++)
    		m[g][g]=0;  //当一个单独合并时,m[i][i]设为0,表示没有积分。
                                                            
    	for(int i=1;i<=n-1;i++)//当相邻的两堆石子合并时,此时的m很容易可以看出是两者之和。
    	{
          int j=i+1;
          m[i][j]=p[i]+p[j];
        }
                                                         
    	for(int r=3; r<=n;r++)//当相邻的3堆以及到最后的n堆时,执行以下循环(r表示考虑到了多堆石子合并的所有情况) 
           for(int i=1;i<=n-r+1;i++)//i表示开始的那一堆,j表示最后的那一堆 
           {
               int j = i+r-1; //j总是距离i r-1的距离                           
               int fin=0;                                  
               for(int b=i;b<=j;b++)//当i到j堆石子合并时最后里面的石子数求和得fin(fin是所有的石子数) 
                   fin+=p[b];
    
               // 此时m[i][j]为i~j堆石子间以m[i][i]+m[i+1][j]+fin结果,这是其中一种可能,不一定是最优
               //要与下面的情况相比较
    
                m[i][j] = m[i+1][j]+fin;//最初的积分情况 
    
               //除上面一种组合情况外的其他组合情况
               for(int k=i+1;k<j;k++)//进行比较 
               {
                   int t=m[i][k]+m[k+1][j]+fin;//后来情况的积分 
                   if(t<m[i][j])
                       m[i][j] = t;
    
               }
           }
            //最终得到最优解
           min=m[1][n]; //最小的情况赋值给min 
           return min;
          
    }
    

    (2)最大得分的求法与最小得分的求法是相同的道理;

    (3)我们回到解法的开始:假设的是石子一次排开求最大得分和最小得分,而题目要求的是:石子以圆形排开,因此我们在主函数中应用了相应方法来达到要求,代码如下:
    int main()
    {
    int stone[N];//每堆石子数
    int min=0;//最小的分初始化
    int max=0;//最大的分初始化
    int n;//石子堆数
    printf(“请输入石子堆数:”);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    printf(“请输入第%d堆石子数:”,i);
    scanf("%d",&stone[i]);
    }
    min= MatrixChain_min(stone,n);//传到子函数
    max= MatrixChain_max(stone,n);//传到子函数

       //因为题目要求圆的原因,要把所有情况都要考虑到,总共有n种情况。
       for(int j=1;j<=n-1;j++)
       {
            int min_cache=0;//积分最小情况 
            int max_cache=0;//积分最大情况
            int cache= stone[1];
            for(int k=2;k<=n;k++)
            {
                stone[k-1]=stone[k];
            }
            stone[n]=cache;
            min_cache= MatrixChain_min(stone,n);
            max_cache= MatrixChain_max(stone,n);
            if(min_cache<min)
               min=min_cache;
            if(max_cache>max)
                max=max_cache;
      }
    
    printf("最小得分:%d\n",min);
    printf("最大得分:%d\n",max);
     return 1;
    

    }
    总的来说就是:在循环中,通过cache这个中间变量,让每一堆石子都有成为第一堆的机会,满足圆形的要求,然后用排序之后的石子调用上面的方法,得到新的得分数,分别与之前的最大得分和最小得分进行比较,得到最终的最大得分和最小得分。

    展开全文
  • 分析:与石子合并只加了一个环形的条件 对于环形问题,如果只是枚举中断点的话,在石子合并的基础上多开一维,时间复杂度是O(n^4) 可以采用一个普遍的方法,就是把环转换成一个链 通过把从1展开的链接在n的后面...

    原题链接- AcWing 

    分析:与石子合并只加了一个环形的条件

    对于环形问题,如果只是枚举中断点的话,在石子合并的基础上多开一维,时间复杂度是O(n^4)

    可以采用一个普遍的方法,就是把环转换成一个链

     

     通过把从1展开的链接在n的后面,这样子枚举的时候枚举以 位置2 断开的链,只需要枚举 以2开始,长度为len的链,就可以枚举n与1相邻的情况了

    状态转移方程基本和石子合并一样,不同点在于环的存在,导致循环枚举不同

    for(int len=1;len<=n;len++)
            for(int l=1;l+len-1<=2*n;l++)
            {//由于模拟中间断点,把前面断开的接到数组后面去,所以最大可能枚举到2n
    
               ...
            }

     

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N=410;
    int a[N];
    int s[N];
    int dp[N][N];
    int g[N][N];
    
    int main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],a[n+i]=a[i];
        
        for(int i=1;i<=2*n;i++) s[i]=s[i-1]+a[i];
        
        memset(dp,0x3f,sizeof dp),memset(g,-0x3f,sizeof g);
        
        for(int len=1;len<=n;len++)
            for(int l=1;l+len-1<=2*n;l++)
            {
                int r=l+len-1;
                if(len==1) dp[l][r]=g[l][r]=0;
                else
                    for(int k=l;k<r;k++)
                    {
                        dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
                        g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
                    }
            }
        int maxv=-0x3f3f3f3f,minv=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
            minv=min(minv,dp[i][i+n-1]),maxv=max(maxv,g[i][i+n-1]);
        cout<<minv<<endl<<maxv<<endl;
        return 0;
        
    }

    展开全文
  • 试设计算法,计算出将N堆石子合并成一堆的最小花费。在解题之前,介绍一下“四边形不等式优化”,关于这个优化方法的证明,csdn以及网上其他博客上详细介绍了很多,查了很多资料还是有点一知半解,再次归纳简述如下...
  • 环形石子合并问题

    千次阅读 2018-09-08 22:47:23
    环形石子合并问题是在普通的相邻石子合并问题的基础上稍加拓展,石子变成了环形的,也就是说每个石子都可能和其左右两边的石子合并。 那么它的dp解法也是基于普通的相邻石子合并问题,不了解的同学可以参考我写过的...
  • 环形石子合并

    2021-04-12 20:35:07
    题目: 题解: 区间dp #include <bits/stdc++.h> using namespace std; int a[205],f[205][205],g[205][205]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&...i&l
  • 环形石子合并 题目链接 题目描述 在一个圆形操场的四周摆放 N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 试设计出一个算法,计算出将...
  • 将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 n 及每堆的石子数,并进行如下计算: ...
  • 环形石子合并(java)

    2020-08-30 17:09:52
    规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 计算出将N堆石子合并成一堆的最小得分和最高得分。 【输入】 第一行为一个正整数N (2≤N≤100); 以下N行,每行一个正整数...
  • 1148环形石子合并

    2018-10-29 13:21:21
    1148.石子合并 时限:1000ms 内存限制:10000K 总时限:3000ms 描述 在一个圆形操场的四周摆放着n堆石子(n&lt;= 100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一...
  • 不仅可以摆成环形,还可以摆成线形(这是属于石子合并问题较简单的情况) 这个问题有最优子结构,因为只要最后的两堆石子的花费最少,那最终的大堆石子花费就最少(因为最后一次合成的花费是确定的,即全部石子数的总和),...
  • 思路:和普通石子合并不同的是可以首位合并那么我们吧数组开2倍后面n+1到2n存储1到n相同的东西,dp[l][r]表示从L-R区间的最大值,每次石子都是有之前的2堆合并的,所以枚举中间点即可,dp[l][r]=max(dp[l][r],dp[l]...
  • 将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 n 及每堆的石子数,并进行如下计算: ...
  • int f[410][410], g[410][410], p[410]; int main() { //freopen("in.txt", "r", stdin); int n; while (cin >> n) { f(i, 1, n)scanf("%d", &p[i]), p[n + i] = p[i]; f(i, 1, 2 * n)p[i] ...l + le
  • 将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 n 及每堆的石子数,并进行如下计算: ...
  • DP - 区间DP - 石子合并 + 环形石子合并 文章目录DP - 区间DP - 石子合并 + 环形石子合并1、石子合并2、环形石子合并 1、石子合并 设有N堆石子排成一排,其编号为1,2,3,…,N。 每堆石子有一定的质量,可以用一个...
  • 环形石子合并问题(动态规划)传统的石子合并问题为:有N堆石子,现要将石子有序的合并成一堆,规定如下:每次只能移动相邻的2堆石子合并,合并花费为新合成的一堆石子的数量,求将这N堆石子合并成一堆的总花费最小...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,040
精华内容 416
关键字:

环形石子合并