首页 > 代码库 > 石子合并 （动态规划）
石子合并 （动态规划）
一．试题
在一个园形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定
每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
编一程序，由文件读入堆数N及每堆的石子数（≤２０），
①选择一种合并石子的方案，使得做N－1次合并，得分的总和最小；
②选择一种合并石子的方案，使得做N－1次合并，得分的总和最大。
例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依
次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３
得分最大的方案为：１４＋１８＋２２＝５４
</pre><pre name="code" class="cpp">#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 105
//定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目
int solve_min(int *p,int n)
{
int i,j,k,r,sum;
int m[N][N];
memset(m,-1,sizeof(m));
for(i=1; i<=n; i++) //当一个单独合并时，m[i][i]设为0，表示没有石子
m[i][i]=0;
for(i=1; i<n; i++) //当相邻的两堆石子合并时，此时的m很容易可以看出是两者之和
m[i][i+1]=p[i]+p[i+1];
for(r=3; r<=n; r++) //当相邻的3堆以及到最后的n堆时，执行以下循环
{
for(i=1; i<=n-r+1; i++)
{
j=i+r-1;
sum=0;
for(k=i; k<=j; k++) //当i到j堆石子合并时最后里面的石子数求和得sum
sum+=p[k];
m[i][j]=m[i+1][j]+sum;
// 此时m[i][j]为i~j堆石子间以m[i][i]+m[i+1][j]+sum结果，这是其中一种可能，不一定是最优
for(k=i+1; k<j; k++)
{
int t=m[i][k]+m[k+1][j]+sum;
if(t<m[i][j])
m[i][j]=t;
}
}
}
return m[1][n];
}
int solve_max(int *p,int n)
{
int i,j,k,r,sum;
int m[N][N];
memset(m,-1,sizeof(m));
for(i=1; i<=n; i++)
m[i][i]=0;
for(i=1; i<n; i++)
m[i][i+1]=p[i]+p[i+1];
for(r=3; r<=n; r++)
{
for(i=1; i<=n-r+1; i++)
{
j=i+r-1;
sum=0;
for(k=i; k<=j; k++)
sum+=p[k];
m[i][j]=m[i+1][j]+sum;
for(k=i+1; k<j; k++)
{
int t=m[i][k]+m[k+1][j]+sum;
if(t>m[i][j])
m[i][j]=t;
}
}
}
return m[1][n];
}
int main()
{
int i,j,k,n,stone[N];
while(scanf("%d",&n)!=-1)
{
for(i=1; i<=n; i++)
{
scanf("%d",&stone[i]);
}
int mmin=solve_min(stone,n);
int mmax=solve_max(stone,n);
for(j=1; j<n; j++)
{
int t=stone[1];
for(k=1; k<n; k++)
{
stone[k]=stone[k+1];
}
stone[n]=t;
int tmin=solve_min(stone,n);
int tmax=solve_max(stone,n);
if(tmin<mmin)
mmin=tmin;
if(tmax>mmax)
mmax=tmax;
}
printf("%d\n%d\n",mmin,mmax);
}
return 0;
}
石子合并 （动态规划）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。