課件題目參考源代碼動(dòng)態(tài)合并石子

1、一.題目描述:在一個(gè)圓形操場(chǎng)的四周擺放著 N 堆石子(N=100),現(xiàn)要將石子有次序地合并成一堆. 規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù)記為該次合并的得分. 編寫一程序,讀入堆棧數(shù) N 及每堆棧的石子數(shù)(=20). (1)選擇一種合并石子的方案,使用權(quán)得做 N-1 次合并,得分的總和最小;(2)選擇一種合并石子的方案,使用權(quán)得做 N-1 次合并,得分的總和最大;【輸入數(shù)據(jù)】第一行為石子堆數(shù) N;第二行為每堆的石子數(shù),每?jī)蓚€(gè)數(shù)之間用一個(gè)空格分隔.【輸出數(shù)據(jù)】從第一至第N 行為得分最小的合并方案. 第 N+1 行是空行.從第 N+2 行到第 2N+1行是得分最大合并方案.

2、 每種合并方案用N 行表示,其中第i 行(1=i=N)表示第i 次合并前各堆的石子數(shù)(依順時(shí)針次序輸出,哪一堆先輸出均可).并的兩堆石子數(shù)以相應(yīng)的負(fù)數(shù)表示.要求將待合輸入輸出范例:輸入: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 /當(dāng)前序列的合并方案 long c; /得分和d; /子序列的堆數(shù);long sumtype101101; /sumtypeij- 子序列i,j

3、的石子總數(shù)Nist101101; /listij - 子序列i,j的合并方案 date101,dt101; /datei - 第 i 堆石子數(shù),dt - 暫存 date i,j,N; /N - 石子堆數(shù), i,j - 循環(huán)變量voidPr(i,j) /遞歸打印子序列i,j的合并過程k,x; /k - 循環(huán)變量,x - 子序列中首堆石子的序號(hào)if(j != 1) /繼續(xù)倒推合并過程Pr(i,listij.d); /倒推子序列的合并過程x=(i+listij.d-1)%N+1; /求子序列中首堆石子的序號(hào)Pr(x,j-listij.d); /倒推子序列的合并過程for(k=1;k0) coutse

4、tw(4)datek;coutn;datei=datei+datex; /原第 i 堆和第 x 堆合并成第 i 堆datex=-datex; /將原第 x 堆從圈內(nèi)去除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+) /當(dāng)前考慮從第 i 堆數(shù)起,順時(shí)針數(shù)j 堆的子序列if(s=1) /合并i,j子序列的得分和初始化 listij.c=MAX_LONG;elselistij

5、.c=0;t=sumtypeij; /最后一次合并的得分為i,j子序列的石子總數(shù)for(k=1;k=j-1;k+) /子序列的石子堆數(shù)依次考慮堆j-1堆x=(i+k-1)%N+1; /求子序列首堆序號(hào)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中選擇得分總和最小(或最大)的一個(gè)子序列k=1;x=list1N.c; for(i=2;i=N;i+)if(s=1 & listiN.cx)k=i; x=listiN.c;Pr(k,N); /由此出發(fā),倒推合并過程coutsetw(4)sumtype1Nendl; /輸出最后一次將石子合并成一堆的石子總數(shù)coutn;/*coutlistkN.cendl;*/voidmain()coutN;cout輸入每堆石子數(shù)：; for(i=1;idatei;for(i=1;i=N;i+) /求每一個(gè)子序列的石子數(shù) 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+) /暫存合并前的各堆石