1、阶段和状态：
很明显的动规，类似“石子合并”或“矩阵相乘”，此题主要不同在于环的处理问题.
环的处理方法：将长为n的环展开为长为2n的链来处理。
a[i]：表示第i颗珠子的头标记；a[n+i]=a[i];
b[i]：表示第i颗珠子的尾标记；b[i]=a[i+1];b[2*n]=a[1];
f[i][j]：表示从第i颗到第j颗珠子合并为一颗珠子释放的最大能量;
矩阵最小连乘积
注意数组范围 f[0..200,0..200];
记忆化搜索
f[i,j]=max{f[i,k]+f[k+1,,j]+p[i]*p[k+1]*p[j+1]
f[i,j]} (i<=k<j)
n:项链上有N颗能量珠 (4<=n<=100)
能量珠有头标记,尾标记 标记对应着某个正整数
每次释放的能量:=1头标记*1尾标记*2尾标记
设计程序,使放出的总能量最大
数组a[i]:第i个珠子的头标记
var
n,i,j,k,ans:longint; ans:最优解 i,j,k:变量
a:array[0..200]of longint; a[i]:第i个珠子的头标记
f:array[0..200,0..200]of longint; f[i,j]:表示从第i颗到第j颗珠子合并为一颗珠子释放的最大能量
begin
readln(n); 读入n
for i:=1 to n do
begin
read(a[i]); 读入数组[a];
a[n+i]:=a[i]; 将长为n的环展开为长为2n的链来处理
end;
for i:=2*n-1 downto 1 do
for j:=i+1 to 2*n do
for k:=i to j-1 do
begin
if f[i,j]<f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1] then f[i,j]:表示从第i颗到第j颗珠子合并为一颗珠子释放的最大能量
f[i,j]:=f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1];
end;
for i:=1 to n do
if f[i,n+i-1]>ans then ans:=f[i,n+i-1]; 选取最优解
writeln(ans);
end.
这也算是一道比较经典的题吧,以后还是要多看几次的.