区间问题：石子合并

【问题简述】n 堆石子围成一圈，每堆石子的量 a[i]已知。每次可以将相邻两堆合并为一堆，将合并后石子的总量记为这次合并的得分。n－1次合并后石子成为一堆。求这 n－1次合并的得分之和可能的最大值和最小值。

（n≤100，1≤i≤n）

(1) 环的处理方法

以某一点作为起点，按顺时针或逆时针的顺序把环上的元素复制两遍。处理时注意起点范围（0～n－1）和最大长度（n）。

例如上面的示例，可以变成：5 9 4 4 5 9 4 4，这样就包含了分别以5、9、4、4为起点的4个环。

(2) 求解

1. 递推思路：计算将第 i 堆至第 j 堆完全合并所能获得的最大得分。这是此题的关键。考虑模拟每种合并后的具体情形是行不通的。把问题变成这样后就好解决了。

2. 划分阶段：以合并的次数作为标准划分阶段。

3. 确定状态：f1(i,j)表示第 i 堆至第 j 堆合并所能获得的最大价值，f2(i,j)表示第 i 堆至第 j 堆合并所能获得的最小价值。

4. 状态转移方程： f1(i,j)＝max{f1(i,k)＋f1(k＋1,j)+d(i,j)}     f2(i,j)＝min{f2(i,k)＋f2(k＋1,j)+d(i,j)}，其中1≤i≤k<j≤n 边界状态：f1(i,i)＝f2(i,i)＝0 d(i,j)表示当次合并的得分，即从 i 到 j 的石子数量，d(i,j)＝a[i]＋a[i+1]＋…＋a[j]，可用前序和求出。

5. 递推时注意，循环的最外层不是 i，也不是 j，而是 j－i！

最后从 f1(1,n)到 f1(n,n+n)，从 f2(1,n)到 f2(n,n+n)，找出最值即可。

#include <cstring> #include <iostream> using namespace std; const int INF = 10000000; inline int d(int i,int j) { return s[j]-s[i-1]; } int f1[101][101],f2[101][101]; int v[201], s[201]; int n;  int main() {   memset(f1, 0, sizeof(f1)); memset(f2, 0, sizeof(f2));  memset(s, 0, sizeof(s));  cin>>n;    for (int i=1;i<=n;i++) {   cin>>v;   v[n+i]=v;   // 把环拉成链   } for (int i=1;i<=n+n;i++) s=s[i-1]+v;  // 前序和     for (int p=1;p<n;p++)   for (int i=1,j=i+p;(i<n+n)&&j<=(n+n);i++,j=i+p)   {    f1[j]=0; f2[j]=INF;    for (int k=i;k<j;k++)    {     f1[j] = max(f1[j], f1[k]+f1[k+1][j]+d(i,j));     f2[j] = min(f2[j], f2[k]+f2[k+1][j]+d(i,j));    }    cout<<"f2["<<i<<"]["<<j<<"]="<<f2[j]<<endl;   }    int r1=0, r2=INF;  for (int i=1;i<=n;i++) {   if (f1[i+n-1]>r1) r1=f1[i+n-1];   if (f2[i+n-1]<r2) r2=f2[i+n-1]; } cout<<r1<<" "<<r2<<endl;

return 0;

}

时间复杂度：O(n3)

(3) 能量项链

【问题简述】有一串能量项链，上有 N 颗能量珠。能量珠有头标记与尾标记。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 m×r×n，新产生的珠子的头标记为 m，尾标记为 n。

现在要把所有的珠子聚合成一个珠子。请你设计一个聚合顺序，使一串项链释放出的总能量最大。

【分析】

思路是相似的——阶段、状态都一样，而得分的方式变了。

1. 设第 i 个珠子的头标记是value[i]，规定所有下标都是从1开始。

2. 状态转移方程：设 f(i,j)为从 i 到 j 这一条链的最大值，那么

f(i,j)＝max{f(i,k)+f(k,j)+value[i]*value[k+1]*value[j+1]}，其中 i≤k＜j    边界条件 f(k,k)＝0。