NOIP 2006 能量项链

想必有部分读者看过《算法导论》中动态规划一章的矩阵乘法，本题和它有相似之处，只不过本题是环状的，需要破环为链。

假设有10个珠子,编号为0到9，先假设他们是链状的。
由题目可以知道，每一步的决策就是把哪两个相邻的珠子合并在一起，那么最后那一步合并前存在两个珠子。
假设在获得最大能量时，前面的一个珠子是由原来k个珠子合成的，那么后面的那个珠子就是后10-k个珠子合成的，此时的能量是0号珠子的头*k号珠子的尾*第10个珠子的尾 + 之前获得的能量。

因此，用f[i][j]表示从第i个珠子开始把j个珠子合成一个珠子可以获得的最大能量，那么，对于链状的珠子，有如下关系式：
f[i][j] = f[i][k] + f[i + k][j - k] + head[i] * head[i + k] * rear[i + j - 1]

当然，也可以用f[i][j]表示把第i号到第j号珠子合并成一个珠子获得的最大能量，不过这种表示方法不太适用于环状情况。

接下来考虑环状珠子的情况，其实只要把上面的i + k变成(i + k) % n,i + j - 1变成(i + j - 1) % n就可以了。

需要注意的是，本题的计算顺序是在for(j)内嵌套for(i)

最后输出的结果是f[i][n]中的最大值。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03
04 struct ball
05 {
06     long h,r;
07 }value[120];
08
09 long f[120][120];
10 int n;
11
12 int main()
13 {
14     int i,j,k;
15     long max,tmp;
16     scanf("%d",&n);
17     for(i = 0;i < n;i ++)
18         scanf("%ld",&value[i].h);
19     for(i = 0;i < n - 1;i ++)
20         value[i].r = value[i + 1].h;
21     value[n - 1].r = value[0].h;
22
23     for(i = 0;i < n;i ++)
24         f[i][1] = f[i][0] = 0;
25
26     for(j = 2;j <= n;j ++)
27         for(i = 0;i < n;i ++)
28         {
29             max = 0;
30             for(k = 1;k < j;k ++)
31             {
32                 tmp = f[i][k] + f[(i + k) % n][j - k] + value[i].h * value[(i + k) % n].h * value[(i + j - 1) % n].r;
33                 if(tmp > max)   max = tmp;
34             }
35             f[i][j] = max;
36         }
37     max = 0;
38     for(i = 0;i < n;i ++)
39         if(f[i][n] > max)   max = f[i][n];
40     printf("%ld\n",max);
41     return 0;
42 }