公告

联系我:我的126邮箱: billhsu。 Locations of visitors to this page
<2008年7月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

  • 随笔 - 41
  • 文章 - 0
  • 评论 - 82
  • 引用 - 0

常用链接

留言簿(16)

随笔分类

随笔档案

相册

Game Dev

搜索

  •  

最新评论

阅读排行榜

评论排行榜

石子合并
附上题目:
在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。
/*
   Name: Stone Problem
   Copyleft: www.graptor.com
   Author: Bill Hsu
   Date: 27-04-08 15:15
*/

#include 
<iostream>
#include 
<string>
#include 
<fstream>

#define MAX 100
#define MAXint 1000
using namespace std;

int i,j;//循环用的
ifstream in("in.txt");
ofstream 
out ("out.txt");
int f[MAX][MAX];//f[i][j]表示从i起取j堆的最大值
int sum[MAX][MAX];//sum[i][j]表示从i起取j堆的和
int num[MAX];

int main()
{
int n;
in >>n;
for(i=1;i<=n;i++)
{
in >>num[i];
sum[i][
1]=num[i];
f[i][
1]=0;
}
//end for

for (j=2;j<=n;++j)
{
cout 
<<endl<<j<<endl<<endl;
for(i=1;i<=n;++i)
{
cout 
<<(sum[i][j]=num[i]+sum[i%n+1][j-1])<<endl;

}
//end for i
}//end for j
int k,x,t;

for (j=2;j<=n;j++)
{
for(i=1;i<=n;i++)
{
f[i][j]
=MAXint;
t
=sum[i][j];
for(k=1;k<=j-1;k++)
{
x
=(i+k-1)%n+1;
if(f[i][k]+f[x][j-k]+t<f[i][j])
f[i][j]
=f[i][k]+f[x][j-k]+t;
}
//end for k
cout <<f[i][j]<<endl;
}
//end for i

}
//end for j

int tmp=f[1][n];
for(j=1;j<=n;++j)
{
if (f[j][n]<tmp)
tmp
=f[j][n];
}
//end for

cout 
<<tmp<<endl;

system(
"pause");
return 0;
}
//end main

posted on 2008-07-24 21:37 Bill Hsu 阅读(643) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理