《石子归并(动态规划).doc》由会员分享，可在线阅读，更多相关《石子归并(动态规划).doc（3页珍藏版）》请在金锄头文库上搜索。
1、动态规划石子合并问题【石子合并】 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 【输入文件】 包含两行，第1 行是正整数n（1=nn then t(i+k) mod n else ti+k 最后一个连第一个的情况处理 si,j最优si,k+st,j-k+sum1,3 sumi,j表示从i开始数j个数的和 end; var n:integer; a:array1.100 of longint; s:array1.100,1.
2、100 of longint; t:array0.100,0.100 of longint; i,j,k,temp,max,min:longint;begin assign(input,shizi.in); reset(input); readln(n); fillchar(t,sizeof(t),0); 计算和数组 for i:=1 to n do read(ai); for i:=1 to n do for j:=1 to n do for k:=i to i+j-1 do begin if kn then temp:=k mod n else temp:=k; ti,j:=ti,j+at
3、emp; end;动态规划求最大得分 fillchar(s,sizeof(s),0); for j:=2 to n do for i:=1 to n do for k:=1 to j-1 do begin if i+kn then temp:=(i+k) mod n else temp:=i+k; 处理环形问题 max:=si,k+stemp,j-k+ti,j; if si,jmax then si,j:=max; end; max:=0; 在最后的阶段状态中找最大得分 for i:=1 to n do if maxn then temp:=(i+k) mod n else temp:=i+k; 处理环形问题 si,j:=si,k+stemp,j-k+ti,j; if minsi,j then min:=si,j; end; si,j:=min; end; min:=maxlongint; 在最后的阶段状态中找最小得分 for i:=1 to n do if minsi,n then min:=si,n; writeln(max); writeln(min);end.
