课件题目参考源代码动态合并石子

1、一.题目描述:在一个圆形操场的四周摆放着 N 堆石子(N=100),现要将石子有次序地合并成一堆. 规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数记为该次合并的得分. 编写一程序,读入堆栈数 N 及每堆栈的石子数(=20). (1)选择一种合并石子的方案,使用权得做 N-1 次合并,得分的总和最小;(2)选择一种合并石子的方案,使用权得做 N-1 次合并,得分的总和最大;【输入数据】第一行为石子堆数 N;第二行为每堆的石子数,每两个数之间用一个空格分隔.【输出数据】从第一至第N 行为得分最小的合并方案. 第 N+1 行是空行.从第 N+2 行到第 2N+1行是得分最大合并方案.

2、 每种合并方案用N 行表示,其中第i 行(1=i=N)表示第i 次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).并的两堆石子数以相应的负数表示.要求将待合输入输出范例:输入:44 5 9 4输出:-4 5 9 -4-8 -5 9-13 -9224 -5 -9 44 -14 -4-4 -1822程序源代码: #include #includeusing namespatd; #define MAX_LONG 0 x7fstruct Node /当前序列的合并方案 long c; /得分和d; /子序列的堆数;long sumtype101101; /sumtypeij- 子序列i,j

3、的石子总数Nist101101; /listij - 子序列i,j的合并方案 date101,dt101; /datei - 第 i 堆石子数,dt - 暂存 date i,j,N; /N - 石子堆数, i,j - 循环变量voidPr(i,j) /递归打印子序列i,j的合并过程k,x; /k - 循环变量,x - 子序列中首堆石子的序号if(j != 1) /继续倒推合并过程Pr(i,listij.d); /倒推子序列的合并过程x=(i+listij.d-1)%N+1; /求子序列中首堆石子的序号Pr(x,j-listij.d); /倒推子序列的合并过程for(k=1;k0) coutse

4、tw(4)datek;coutn;datei=datei+datex; /原第 i 堆和第 x 堆合并成第 i 堆datex=-datex; /将原第 x 堆从圈内去除voidsolve(s)i,j,k; long t,x;for(i=1;i=N;i+) /仅含一堆石子的序列不存在合并listi1.c=0;listi1.d=0;for(j=2;j=N;j+) /顺推含堆,含堆含 N 堆石子的各子序列的合并方案for(i=1;i=N;i+) /当前考虑从第 i 堆数起,顺时针数j 堆的子序列if(s=1) /合并i,j子序列的得分和初始化 listij.c=MAX_LONG;elselistij

5、.c=0;t=sumtypeij; /最后一次合并的得分为i,j子序列的石子总数for(k=1;k=j-1;k+) /子序列的石子堆数依次考虑堆j-1堆x=(i+k-1)%N+1; /求子序列首堆序号if(s=1 & listik.c+listxj-k.c+tlistij.c)/若该合并方案为目前最佳,则记下listij.c=listik.c+listxj-k.c+t; listij.d=k;/在子序列1,N,2,N,N, N中选择得分总和最小(或最大)的一个子序列k=1;x=list1N.c; for(i=2;i=N;i+)if(s=1 & listiN.cx)k=i; x=listiN.c;Pr(k,N); /由此出发,倒推合并过程coutsetw(4)sumtype1Nendl; /输出最后一次将石子合并成一堆的石子总数coutn;/*coutlistkN.cendl;*/voidmain()coutN;cout输入每堆石子数：; for(i=1;idatei;for(i=1;i=N;i+) /求每一个子序列的石子数 sumtype sumtypei1=datei;for(j=2;j=N;j+) for(i=1;i=N;i+)sumtypeij=datei+sumtypei%N+1j-1;for(i=1;i=N;i+) /暂存合并前的各堆石