dp 石子合并问题

￡神魔★判官ぃ 2022-08-18 00:58 127阅读 0赞

石子合并问题：

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

两堆价值之和，求最终将所有的石子合并成一堆之后的代价最小值。

问题一：n堆石子排成一条直线

这个问题比较简单，类似与矩阵连乘的问题。

dp\[n\]\[m\] 为合并n和m之间的石子的代价

则有dp\[i\]\[j\] = 0 , i==j

dp\[n\]\[m\] = min(dp\[n\]\[k\]+dp\[k+1\]\[m\]) + sum(n,m)  n<=k<m;

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const int INF = 1<<20 ;
    const int maxn = 105 ;
    int sum[maxn];
    int dp[maxn][maxn];
    int n,a[maxn];
    
    int main()
    {
        while(scanf("%d",&n)!=EOF)
        {
            memset(sum,0,sizeof(sum));
            scanf("%d",&a[0]);
            sum[0]=a[0];
            for(int i = 1 ; i < n ; i++)
            {
                scanf("%d",&a[i]);
                sum[i] = sum[i-1] + a[i] ;
            }
            for(int i = 0 ; i < n ; i++)
            {
                dp[i][i] = 0 ;
            }
            for(int v = 1 ; v < n ; v++)
            {
                for(int i = 0 ; i < n-v ; i++)
                {
                    int j = i+v ;
                    int sumij = sum[j] - (i > 0 ? sum[i-1] : 0 ) ;
                    dp[i][j] = INF ;
                    for(int k = i ; k < j ; k++)
                    {
                        dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sumij);
                    }
                }
            }
            printf("%d\n",dp[0][n-1]);
        }
        return 0;
    }

//直线取石子的平行四边形的优化
    
    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    const int INF = 1 << 30;
    const int N = 1005;
    
    int dp[N][N];
    int p[N][N];
    int sum[N];
    int n;
    
    int getMinval()
    {
        for(int i=1; i<=n; i++)
        {
            dp[i][i] = 0;
            p[i][i] = i;
        }
        for(int len=1; len<n; len++)
        {
            for(int i=1; i+len<=n; i++)
            {
                int end = i+len;
                int tmp = INF;
                int k = 0;
                for(int j=p[i][end-1]; j<=p[i+1][end]; j++)
                {
                    if(dp[i][j] + dp[j+1][end] + sum[end] - sum[i-1] < tmp)
                    {
                        tmp = dp[i][j] + dp[j+1][end] + sum[end] - sum[i-1];
                        k = j;
                    }
                }
                dp[i][end] = tmp;
                p[i][end] = k;
            }
        }
        return dp[1][n];
    }
    
    int main()
    {
        while(scanf("%d",&n)!=EOF)
        {
            sum[0] = 0;
            for(int i=1; i<=n; i++)
            {
                int val;
                scanf("%d",&val);
                sum[i] = sum[i-1] + val;
            }
            printf("%d\n",getMinval());
        }
        return 0;
    }

问题二：n堆石子围成一圈

如果石子是排成圆形，其余条件不变，那么最优值又是什么呢？  
因为圆形是首尾相接的，初一想，似乎与直线排列完全成了两个不同的问题。因为每次合并后我们都要考虑最后一个与第一个的合并关系。直线版的矩阵连乘对角线式的最优子结构不见了。f(i, j)表示i-j合并的最优值似乎并不可行，因为我们可以得到的最优值第一步就是第一个与最后一个合并，那么f(i, j)并不能表示这种关系。  
修改一下，f(i, j)表示从第i个开始，合并后面j个得到的最优值。sum(i, j)表示从第i个开始直到i+j个的数量和。那么这个问题就得到解决了。注意要把其看成环形，即在有限域内的合并。  
  
破圆化直：将圆形的石子归并化为直线型石子归并。  
方法是：将原来的石子长度增加一倍，加在原来的后面，a\[1\]~a\[n\],a\[1\]~a\[n\],  
求从1，2，3，~n开始的n个合并的最小值，最其中一个最小值即可。

![Image 1][]

#include <iostream>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    const int INF = 1 << 30;
    const int N = 205;
    
    int mins[N][N];
    int maxs[N][N];
    int sum[N],a[N];
    int minval,maxval;
    int n;
    
    int getsum(int i,int j)
    {
        if(i+j >= n) return getsum(i,n-i-1) + getsum(0,(i+j)%n);
        else return sum[i+j] - (i>0 ? sum[i-1]:0);
    }
    
    void Work(int a[],int n)
    {
        for(int i=0;i<n;i++)
            mins[i][0] = maxs[i][0] = 0;
        for(int j=1;j<n;j++)
        {
            for(int i=0;i<n;i++)
            {
                mins[i][j] = INF;
                maxs[i][j] = 0;
                for(int k=0;k<j;k++)
                {
                    mins[i][j] = min(mins[i][j],mins[i][k] + mins[(i+k+1)%n][j-k-1] + getsum(i,j));
                    maxs[i][j] = max(maxs[i][j],maxs[i][k] + maxs[(i+k+1)%n][j-k-1] + getsum(i,j));
                }
            }
        }
        minval = mins[0][n-1];
        maxval = maxs[0][n-1];
        for(int i=0;i<n;i++)
        {
            minval = min(minval,mins[i][n-1]);
            maxval = max(maxval,maxs[i][n-1]);
        }
    }
    
    int main()
    {
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            sum[0] = a[0];
            for(int i=1;i<n;i++)
                sum[i] = sum[i-1] + a[i];
            Work(a,n);
            printf("%d %d\n",minval,maxval);
        }
        return 0;
    }

/*
    Auther:LIUYAN
    2015.12.02
    
    4 4 4 5 9
    6 3 4 6 5 4 2
    */

[Image 1]: