石子合并问题

[效云 李]

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

编程任务：
对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。
Input

输入包括多组测试数据，每组测试数据包括两行。

第1 行是正整数n，1<=n<=100，表示有n堆石子。
第2行有n个数，分别表示每堆石子的个数。
Output

对于每组输入数据，输出两行。

第1 行中的数是最小得分；第2 行中的数是最大得分。
Sample Input

4
4 4 5 9

Sample Output

43
54

[效云 李]

编程环境VS2005:
代码：
// 动态规划-石子合并问题.cpp : Defines the entry point for the console
application.
//

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int weight(int i,int j,vector<int> v,int n)
{
int temp=0;
int k=0;
if(j<n)
{
for(k=i;k<=j;++k)
{
temp+=v[k];
}
}
else
{
for(k=i;k<n;++k)
{
temp+=v[k];
}

for(k=0;k<=j%n;++k)
{
temp+=v[k];
}
}

return temp;
}
void calculate(vector<vector<int> >& m,vector<int> v,int n,int tag)
{
int r=0,i=0;
for(r=2;r<=n;++r)//链长
for(i=0;i<n;++i)//链起点
{
int j=i+r-1;//尾
int temp=weight(i,j,v,n);//处理j>n
m[i%n][j%n]=m[(i+1)%n][j%n]+temp;//初始化m[i][j]
for(int k=i+1;k<j;k++)
{
int t=m[i%n][k%n]+m[(k+1)%n][j%n]+temp;
if(tag==1)
{
if(t<m[i%n][j%n])m[i%n][j%n]=t;
};
if(tag==0)
{
if(t>m[i%n][j%n])m[i%n][j%n]=t;
};
}

}
}

int _tmain(int argc, _TCHAR* argv[])
{
int n=0;
ifstream finput;
finput.open("input.txt");
finput>>n;

vector<int> v(n+1);
int i=0;
int temp=0;
for(i=0;i<n;i++)
{
finput>>temp;
v[i]=temp;
}
finput.close();

vector<vector<int> > m(n,vector<int>(n));

int tag=1;//tag=1,为求最小，tag=0,为求最大
calculate(m,v,n,tag);

ofstream foutput;
foutput.open("output.txt");

int result_min=m[0][n-1];
for(i=1;i<n;++i)
{
if(m[i][i-1]<result_min)result_min=m[i][i-1];
}

foutput<<result_min<<endl;

tag=0;
calculate(m,v,n,tag);
int result_max=m[0][n-1];
for(i=1;i<n;++i)
{
if(m[i][i-1]>result_max)result_max=m[i][i-1];
}
foutput<<result_max;
foutput.close();

return 0;
}

已编译运行通过，望指教，谢谢

[higer]

现在我还没做这道题，等我做完再好好看看你的算法。

[higer]

这道题其实跟“矩阵连乘”问题几乎是一样的，下面是我的代码，在VC6.0和gcc 2.95.3-5下测试通过：
/
************************************************************************/
/* 石子合并问题 */
/
************************************************************************/
#include "stdio.h"
#include <string.h>
int A[100][100];//最小分数
int B[100][100];//最大分数
int m[100][100];//石子数
int max=0,min=0;
void calculate(int n){
int r=0,i=0,k=0;
for(r=2;r<=n;r++)
for(i=0;i<n-r+1;i++)
{
int j=i+r-1;
A[i][j]=A[i+1][j]+m[i][j];
B[i][j]=B[i+1][j]+m[i][j];
for(k=i+1;k<j;k++){
int t1=A[i][k]+A[k+1][j]+m[i][j];
int t2=B[i][k]+B[k+1][j]+m[i][j];
if(t1<=A[i][j]) A[i][j]=t1;
if(t2>B[i][j]) B[i][j]=t2;
}
}
}
int sum(int* m,int i,int j){
int all=0;
int k=0;
for(k=i;k<=j;k++)
all+=m[k];
return all;
}
int main(){
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
memset(m,0,sizeof(m));
int a[100];
int n=0;
scanf("%d",&n);
int i=0,j=0;
for (i=0;i<n;i++) {
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
m[i][j]=sum(a,i,j);
}
calculate(n);
printf("%d\n%d\n",A[0][n-1],B[0][n-1]);

return 0;
}

[higer]

看了一些李效云的算法，我想知道为什么用calculate计算之后，还有用

int result_min=m[0][n-1];
for(i=1;i<n;++i)
{
if(m[i][i-1]<result_min)result_min=m[i][i-1];
}

来判断一遍？

On Apr 11, 6:48 pm, 效云 李 <lixiaoyun...@gmail.com> wrote:

[李效云]

     for(r=2;r<=n;r++)
               for(i=0;i<n-r+1;i++)

？？？？
不用说了吧，讨论过了，

2009/4/13 higer <higerin...@gmail.com>

[higer]

程序修改：
之前我的程序没有考虑到“圆形操场”可以循环合并的问题，这次加上了。

/
************************************************************************/
/* ʯ×Ӻϲ
¢ÎÊÌâ */

/
************************************************************************/
#include "stdio.h"
#include <string.h>

int A[100][100];//×îС·ÖÊý
int B[100][100];//×î´ó·ÖÊý
int m[100][100];//ʯ×ÓÊý

int max=0,min=0;
void calculate(int n){
int r=0,i=0,k=0;
for(r=2;r<=n;r++)

for(i=0;i<n;i++)
{
int j=(i+r-1)%n;
A[i][j]=A[(i+1)%n][j]+m[i][j];
B[i][j]=B[(i+1)%n][j]+m[i][j];
for(k=i+1;k<(i<j?j:(j+n));k++){
int t1=A[i][k%n]+A[(k+1)%n][j]+m[i][j];
int t2=B[i][k%n]+B[(k+1)%n][j]+m[i][j];

if(t1<=A[i][j]) A[i][j]=t1;

if(t2>=B[i][j]) B[i][j]=t2;

}
}
}
int sum(int* m,int i,int j){
int all=0;
int k=0;
for(k=i;k<=j;k++)
all+=m[k];
return all;
}
int main(){
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
memset(m,0,sizeof(m));
int a[100];
int n=0;
scanf("%d",&n);
int i=0,j=0;
for (i=0;i<n;i++) {
scanf("%d",&a[i]);
}

int all=sum(a,0,n-1);

for(i=0;i<n;i++)
for(j=0;j<n;j++)
{

if(i<=j) m[i][j]=sum(a,i,j);
else m[i][j]=all-m[j][i]+a[i]+a[j];
}
calculate(n);
int min=A[0][n-1],max=B[0][n-1];
for (i=1;i<n;i++) {
if(A[i][(i+n-1)%n]<min) min=A[i][(i+n-1)%n];
if(B[i][(i+n-1)%n]>max) max=B[i][(i+n-1)%n];
}
printf("%d\n%d\n",min,max);

return 0;
}

[苏峰]

恩，这应该就正确了，只是不知道测试数据的范围，如果较大,那么结果 得用long long ,
如果不大的话一个byte 数组即可。

2009/4/14 higer <higerin...@gmail.com>

[zhong nanhai]

这是王晓东课本上面的题，所以他并没有对数据作严格的规范，如果是正规的Online Judge（比如Google code jam或Top
coder），这的确要好好考虑考虑了。