能量项链解题报告1、 环的处理1） 枚举断点，处理链例如：此图为一个环，如下图，可在a、b、c、d、e、五处做断点，处理五个环。即：2-3-4-5-1、3-4-5-1-2、4-5-1-2-3、5-1-2-3-4、 1-2-3-4-5，求出最优解2） 处理若干个链处理若干个链，即处理上述五个链，并求出最优值。3） 处理长链即将此环当作链，并复制一遍，在截取，即可，例如：1-2-3-4-5这个环，将其复制为1-2-3-4-5-1-2-3-4-5，成为长链，再截取，如下|1-2-3-4-5|-1-2-3-4-5 1-|2-3-4-5-1|-2-3-4-5 1-2-|3-4-5-1-2|-3-4-5 1-2-3-|4-5-1-2-3|-4-5 1-2-3-4-|5-1-2-3-4|-5 处理五个“ | ”内的链，求最优值。总结：我认为，其实最后都是殊途同归，都是求出多个链，找到最优值。2、 记录珠子的首尾用 pi表示第 i 个珠子的左值用 pi+1表示第 i 个珠子的右值例如 : P内的值 :n1 n2 n3 n4 n5 i ： 1 2 3 4 5 此时，珠子为：此时，第1 颗珠子的左值即p1=n1 ，右值为p1+1 即 p2=n2 ，以此类推动态规划F(i,j)表示 i-j个珠子合并的最优值F(1,n) 即为 1-n 个珠子合并的最优值1231.max(1,)nnp p pppFn即为所求F(i,j)分为三部分：左、右、左右合并若 k 为分界线，则F(i,j)=F(i,k)+F(k+1,j)+pi*pk+1*pj 所以10 ( ,)max( ,1, *1 *1) ikjij fijD ata i kD ata kjp ip kp jij3、 实现1)递归Procedure f(i,j:Integer); Var max,maxk,k:LongInt; Begin If i=j Then Begin Datai,j:=0;exit; End; Max:=-1; For k:=i To j-1 Do Begin If Datai,k=-1 Then f(i,k); If Datak+1,j=-1 Then f(k+1,j); Maxk:=Datai,k+Datak+1,j+(pi*pk+1*pj+1); If maxDataj,i+jThen Dataj,i+j:=maxk; End; End; End; 4、 源代码 Const Infile = energy.in; Outfile = energy.out; Var /定义变量n,i,m:Integer; p:Array1.101Of INteger; t:Array1.200Of Integer; Data:Array1.100,1.100Of LongInt; z:LongInt; Procedure f(i,j:Integer); /子程序Var max,maxk,k:LongInt; /定义局部变量Begin If i=j Then Begin /判断 ij是否相等Datai,j:=0; Exit; End; max:=-1; /对 max赋初值For k:=i to J-1 Do Begin /循环求最优解If Datai,k=-1 Then f(i,k); /递归求左串If Datak+1,j=-1 Then f(k+1,j); /递归求右串maxk:=Datai,k+Datak+1,j+pi*pk+1*pj+1; /求值If maxkmax Then max:=maxk; /比较大小End; Datai,j:=max; /对 Data 赋值End; Begin Assign(input,infile); /建立联系Reset(input); /读打开REadLn(n); /读入珠子数FOr i:=1 TO n Do REad(pi); /读入值Close(input); /关闭输入文件For i:=1 TO n Do ti:=pi; /复制串 p For i:=1 TO n Do ti+n:=pi; z:=-1; /初始化 z For m:=1 TO n Do Begin /循环求环的最优解Fillchar(Data,sizeof(Data),$ff); /初始化 Data For i:=1 To n+1 Do pi:=ti+m-1; /循环链f(1,n); /求值If Data1,nz Then z:=Data1,n; /比较大小纪录最大值End; Assign(output,outfile); /建立联系Rewrite(output); /写打开WriteLn(z); /输出Close(output); /关闭输出文件End.