dp 石子合并问题-蒲公英云

dp 石子合并问题

石子合并问题：

有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
*/