题目描述
在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。
对于给定n堆石子,计算合并成一堆的最小得分和最大得分。
输入
输入数据的第1行是正整数n,1≤n≤100,表示有n堆石子。第二行有 n个数,分别表示每堆石子的个数。
输出
输出数据有两行,第1行中的数是最小得分,第2行中的数是最大得分。
样例输入
4
4 4 5 9
样例输出
43
54
参考代码
#include<stdio.h>
int N;
//æå¤100å ç³å:N=100
int num[200]={0};
int max=-0x3f3f3f3f;
int stone_merge()
{
int score[200][101]={0};
//l[i][j]:ä»ç¬¬iå ç³åèµ·å并nå ç³åçæå°å¾å
int score2[200][101]={0};
int n,i,k,temp,t2;
for (i=0;i<2*N;i++)
{
score[i][1]=0;
//ä¸å ç³åå并å¾å为0
score2[i][1]=0;
}
for (n=2;n<=N;n++)//å并nå ç³å
{
for (i=0;i<=2*N-n;i++)//ä»ç¬¬i对å¼å§å并(æä¸æ¬¡éå¤è¿ç®ï¼ä½çå»äºå¾ªç¯åæ°ï¼ç®åäºç¨åº)
{
score[i][n]=score[i][1]+score[i+1][n-1];
score2[i][n]=score2[i][1]+score2[i+1][n-1];
for (k=2;k<n;k++)//åå
{
temp=score[i][k]+score[k+i][n-k];
t2=score2[i][k]+score2[k+i][n-k];
if(temp<score[i][n])
score[i][n]=temp;
//å(i,n)åå两é¨åçå¾å
if(t2>score2[i][n])
score2[i][n]=t2;
}
for (k=i;k<i+n;k++)
{
score[i][n]+=num[k];
//å ä¸æ¤æ¬¡å并å¾å
score2[i][n]+=num[k];
}
}
}
int min=2147483647;
//int(4ä½)æ大å¼ä¸º2147483647
for (i=0;i<N;i++)
{
if(score[i][N]<min)
min=score[i][N];
//ä»ç¬¬iå å¼å§åNå ç³åï¼çæå°å并å¾å
if(score2[i][N]>max)
max=score2[i][N];
}
return min;
}
int main()
{
int min_count;
scanf("%d",&N);
//Nå ç³å
for (int i=0;i<N;i++)
scanf("%d",&num[i]);
//æ¯å ç³åçæ°é
for (int i=N;i<2*N;i++)
num[i]=num[i-N];
//å¤å¶ä¸åï¼åç®ç¯å½¢è®¡ç®ï¼Nå ç³åæ¯å´æä¸ä¸ªç¯çï¼
if(N==1) min_count=0; else if(N==2) min_count=num[0]+num[1]; else min_count=stone_merge();
printf("%dn",min_count);
printf("%dn",max);
return 0;
}
解析
暂无