我的算法有问题，它陷入了局部最优。开了一天的会，很累，今天就不调试了。
我制作了一组随机测试数组，通过对比你我代码的输出结果发现了上面的问题。也许你能用得着。
别让这贴沉了，一定要搞定它

26 17
2 0 1 1 2 0 2 2 1 1 2 1 0 1 1 0 0 1 2 2 2 2 0 1 0 0
17 16
2 1 2 2 1 2 0 2 0 2 2 1 0 2 2 2 1
50 47
2 1 0 1 2 0 2 0 0 1 1 0 1 0 1 1 1 1 1 2 2 1 2 2 2 0 1 0 2 0 0 0 0 1 1 1 2 1 0 2 1 1 2 1 0 2 2 2 0 0
23 5
2 0 1 2 1 0 1 0 1 0 1 0 2 0 2 2 1 1 0 2 1 0 1
14 13
0 1 0 2 2 1 0 2 1 0 1 1 2 1
44 37
0 0 2 0 1 0 2 1 2 0 1 2 2 0 2 0 1 2 0 1 1 1 1 0 1 1 2 2 1 0 0 2 0 1 0 0 2 1 0 1 2 1 0 0
45 24
2 2 0 0 1 1 0 2 2 1 2 2 1 1 1 2 2 0 2 2 1 1 1 2 2 1 1 0 0 2 1 2 0 2 2 2 1 1 0 0 0 2 0 0 1
49 15
1 1 0 0 0 1 1 1 0 0 0 2 2 1 1 2 0 1 0 2 2 0 0 0 2 0 2 0 0 0 1 1 1 0 2 1 1 1 2 1 0 0 0 0 2 2 1 0 2
18 9
1 2 0 0 2 1 1 1 2 1 2 1 2 1 0 1 1 0
14 9
1 0 2 1 0 2 2 2 0 2 1 2 2 2
13 9
0 2 2 2 2 1 0 2 0 1 2 2 2
18 10
0 2 2 1 1 0 1 2 2 1 1 0 2 1 1 0 0 0
38 37
2 1 1 2 1 0 0 1 0 0 0 0 1 1 2 0 0 0 1 1 0 1 0 1 1 0 0 2 0 2 1 0 0 2 2 0 1 1
24 20
2 1 0 0 1 2 1 2 0 2 2 0 1 2 2 0 2 2 1 1 1 2 2 2
49 3
2 2 0 2 2 1 0 1 0 1 2 2 2 1 0 0 0 2 1 0 1 1 1 2 0 0 1 2 2 0 1 0 0 0 2 1 0 1 0 2 1 2 1 2 1 0 2 0 0
49 5
1 2 1 1 0 2 0 0 2 1 1 2 1 0 1 2 0 0 1 0 1 2 1 0 1 0 0 1 1 2 2 2 2 2 0 0 2 0 1 1 1 1 2 2 1 1 2 2 2
50 47
1 1 0 2 2 2 2 0 1 2 1 2 0 0 2 2 0 0 0 1 2 1 1 1 0 0 1 1 2 1 2 1 2 0 0 2 2 1 1 1 1 2 1 2 2 1 2 2 1 2
41 24
1 1 0 1 2 0 1 0 2 2 2 2 1 1 2 1 1 2 0 0 1 2 2 1 1 2 0 1 2 2 2 0 1 1 2 1 1 1 2 0 0
23 21
0 0 2 1 2 2 0 1 1 1 1 0 0 2 1 1 1 1 1 1 2 2 0
44 23
0 2 0 2 0 1 1 1 2 0 1 1 1 2 2 2 2 1 1 0 1 2 2 2 1 2 0 2 0 0 0 1 2 1 0 2 2 1 2 1 2 2 1 1
43 7
2 2 2 0 1 1 0 0 0 0 2 2 1 2 0 2 0 0 1 0 2 2 2 1 2 2 0 1 1 1 0 0 0 0 0 1 2 0 0 0 2 0 2
20 19
2 2 1 2 2 0 0 0 2 2 2 2 2 1 1 1 0 1 2 2
45 29
0 1 0 1 1 2 0 2 0 2 2 0 0 0 1 1 0 1 2 1 1 0 2 1 2 0 2 2 2 1 2 1 0 2 0 1 2 2 2 2 0 2 1 0 1
27 7
2 2 2 1 1 1 1 0 1 0 1 2 0 1 1 0 0 1 2 2 0 2 1 2 2 0 0
46 22
2 1 1 0 2 1 1 0 2 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 2 1 0 2 2 0 0 0 0 0 2 0 0 0 1 0 0 0 2 0 0
33 7
2 2 0 1 0 0 2 2 1 1 1 2 2 1 1 2 1 0 2 0 2 2 2 1 0 1 0 2 0 0 0 2 2
16 5
2 1 2 0 0 1 1 2 0 1 2 1 2 2 1 0
22 4
1 0 1 0 2 0 2 2 0 1 2 2 1 2 1 0 1 1 1 1 1 1
25 16
0 2 2 0 1 1 1 1 1 2 2 1 1 2 0 0 2 1 2 2 2 0 2 2 2
8 2
0 0 1 0 1 2 2 0
27 15
2 1 1 0 2 1 0 0 0 0 1 0 2 0 0 0 2 0 0 1 1 1 0 0 0 1 1
15 7
0 0 0 2 2 1 1 1 1 0 2 2 1 1 2
13 10
0 0 0 1 0 1 0 1 0 2 2 1 2
43 14
1 0 2 1 0 1 2 1 1 2 2 0 0 0 2 2 1 2 2 2 1 1 1 2 0 1 0 1 2 2 0 1 2 2 1 2 0 0 1 1 1 0 2
35 18
2 0 2 0 1 0 1 2 2 2 2 2 1 1 2 2 2 0 2 0 0 1 1 2 1 1 2 1 1 1 2 1 1 1 0
39 16
2 0 1 1 1 0 0 2 0 2 2 2 2 2 1 1 2 2 1 0 0 1 0 1 2 1 2 1 2 2 1 2 0 2 2 0 1 2 2
46 43
0 2 0 2 0 2 2 2 2 1 2 2 0 2 1 1 0 1 0 1 1 1 1 0 0 0 1 0 2 1 1 0 2 2 1 1 0 0 2 1 0 0 2 2 0 2
23 1
0 1 0 2 2 2 2 1 1 0 2 0 2 0 0 1 2 2 0 2 2 2 2
50 20
1 0 2 2 0 1 2 0 2 2 2 2 2 1 0 2 2 1 1 2 1 2 2 1 0 0 2 2 1 0 2 0 2 0 0 1 2 1 0 0 0 0 0 2 1 1 0 0 2 2
35 3
0 2 1 0 1 0 0 0 2 0 1 1 0 2 0 0 2 1 1 0 0 0 0 0 2 1 0 2 1 1 1 0 2 0 1
34 9
2 1 2 2 2 1 1 2 0 0 0 2 0 0 2 2 0 2 2 2 0 1 2 1 1 1 1 0 1 0 2 2 1 1
21 21
0 1 1 0 1 2 1 1 2 1 0 2 1 0 2 1 0 1 1 1 2
47 27
1 2 2 0 2 0 0 0 2 0 1 0 1 1 0 0 1 2 1 0 2 2 1 2 2 2 0 0 2 2 2 2 1 2 1 1 0 0 0 1 2 1 2 0 2 1 1
32 29
1 2 1 1 2 2 2 2 0 2 0 0 0 2 0 2 2 0 1 0 0 2 0 2 2 1 1 2 2 0 2 1
17 2
0 2 0 0 2 2 1 0 2 1 2 2 2 1 1 0 1
50 13
0 1 1 0 2 2 2 0 2 2 0 2 1 0 0 2 0 1 1 2 1 1 1 0 2 2 0 0 2 1 0 2 1 1 2 0 2 1 0 0 1 1 0 1 0 1 2 0 0 2
11 9
2 2 1 0 0 1 0 1 0 0 1
13 11
0 0 0 1 1 0 0 2 1 2 1 0 1
39 6
1 1 1 0 2 1 2 2 2 1 2 0 2 2 1 2 1 0 1 2 0 1 0 1 0 0 0 1 0 0 1 2 0 1 0 0 0 2 0
26 16
0 2 0 0 0 0 1 2 1 0 1 0 2 0 0 1 1 2 0 1 0 2 0 0 2 0
46 41
0 0 2 0 1 0 2 1 0 0 2 2 2 0 2 1 1 1 0 0 0 2 0 0 2 2 2 0 1 1 1 1 2 2 1 2 0 0 1 2 2 0 0 0 0 0
29 24
1 1 1 2 0 1 0 1 1 2 1 0 0 2 1 2 0 2 1 2 2 0 1 2 2 1 1 2 1
26 14
2 1 0 2 0 0 1 1 2 0 0 0 2 2 0 0 1 2 2 0 1 2 1 2 1 1
19 16
0 0

本来生成了100组数据，可惜太大发不上来，删了一部分。

还是没解决。。想不通为什么会WA

终于搞定了。呵呵。原理很简单，但细节的控制需要非常谨慎的计算，花了很多时间在这上面。
下面是AC代码。这是我记忆中使用嵌套层数最多的一次，为了保持算法级原理的清晰，我没有对代码做优化。包括数组e，它实际使用的部分也只有约总空间的1/6。

#include<stdio.h>
#define SIZE    50
long long E(int *a, int n, int m)
{
    long long e[SIZE][SIZE][SIZE], max, t;
    int i, j, k, u, v;

    for(i = 0; i < n; i++) e[0][i][i] = a[i];

    for(i = 0; i < n; i++)
    for(j = i + 1; j < n; j++)
        e[0][i][j] = e[0][i][j - 1] * e[0][j][j];
    for(k = 1; k < m; k++)
    for(i = 0; i < n - k; i++)
    for(j = i + k; j < n; j++)
    {
        max = 0;
        for(u = 0; u < k; u++)
        for(v = i + u; v <= j - k + u; v++)
        {
            t = e[u][i][v] + e[k - u - 1][v + 1][j];
            if(t > max) max = t;
        }
        e[k][i][j] = max;
    }

    return e[m - 1][0][n - 1];
}
int main()
{
    int a[SIZE], n, m, i;
    while(scanf("%d %d", &n, &m), n)
    {
        for(i = 0; i < n; scanf("%d", &a[i++]));
        printf("%lld\n", E(a, n, m));
    }
    return 0;
}

看了你的代码，思路应该差不多，用f[i,k,j]表示在 k-j中插入i个分割，所以f[m-1,0,n-1]就是答案。

然后我生成了大量个随机数据，每次生成500个，然后用你我的程序输出结果对比，试了10次。。然后发现都是一样的

纠结啊。但我觉得你的程序应该是还可以优化的，现在的时间复杂度偏大，只不过这个数据不是很大

分析的角度不同，构造出的算法也不同。同是动态规划的思想，你我的思考角度不一样。

呵呵，别介意，玩ACM的乐趣就在于思考的过程。今天AC之前我一直没看你的算法，毕竟靠自己的努力通过获得的成就感更高。

看完你的算法思想后，我表示非常赞同，它是我构造的最优子结构的一个子集，排除了我的算法结构中的重复部分。也开拓了我的思路

之后按照你的想法，用我的理解重写了一遍。AC，时间为1（我上面的代码消耗时间是27，也不知道它的时间单位是什么，大概是毫秒）。时间复杂度上比我的降低了一次幂。

你对比一下，找找你代码WA的原因吧。

#include<stdio.h>
#define SIZE    50
long long E(int *a, int n, int m)
{
    long long f[SIZE][SIZE], p[SIZE][SIZE], max, t;
    int i, j, k;

    //p[i][j]表示从i到j的元素乘积，i j的下标从0开始
    for(i = 0; i < n; i++) p[i][i] = a[i];

    for(i = 0; i < n; i++)
    for(j = i + 1; j < n; j++)
        p[i][j] = p[i][j - 1] * p[j][j];

    //f[i][j]的意义与你的定义相同，下标从0开始
    for(i = 0; i < n; i++) f[i][0] = p[0][i];

    for(j = 1; j < m; j++)
    for(i = j; i < n; i++)
    {
        max = 0;
        for(k = j - 1; k < i; k++)
        {
            t = f[k][j - 1] + p[k + 1][i];
            if(t > max) max = t;
        }
        f[i][j] = max;
    }

    return f[n - 1][m - 1];
}
int main()
{
    int a[SIZE], n, m, i;
    while(scanf("%d %d", &n, &m), n)
    {
        for(i = 0; i < n; scanf("%d", &a[i++]));
        printf("%lld\n", E(a, n, m));
    }
    return 0;
}

和你讨论问题很愉快

好久没做题了，再看题目发现都不会做了。

冒个泡，楼主好，杨大哥好！

经对比测试，我的程序在求k--j段的乘积有错误（虽然这个实现很简单，但我还真找不到，难道是当局者迷...)，换成你的方法就ac了，感觉还真有点诡异、、、

还有一个下标的问题，c语言中数组一般以0为下标，但我最初学的是pascal语言，所以习惯了用1做下表，虽然有时候会尽量去适用0做下标，但一遇到复杂点的问题就感觉还是用1做下标比较舒服，不知道这种编程习惯好不好。。

不过非常感谢了，难的这么上心，一起进步

楼上小蔡好，czz还不知道怎么称呼？

当局者迷，这个词好。我用了一晚上的时间来调整那个五层嵌套中最里的两个的循环起始终止值。你关于tpow的做法感觉也没问题，应该还是细节的控制中出了偏差，还是建议你找找出错的原因，这上面我就不帮忙了呵呵。我把ACM当作休闲娱乐，以前一个人寻开心，遇到老杨（他比我小很多）、李志、小蔡，还有你之后，一起讨论相互切磋我觉得更开心。每个人的思想不同，相互借鉴一下很能开拓思路。

至于数组下标的问题，这就是个习惯的问题，不影响算法的本质，VB下就是从1开始的。不过将来打算常用类C的语言还是建议习惯从0开始，可以节省点空间。

关于这一题我一直想找一个线性算法来着，但结果总是陷入局部最优解，之前的那个WA代码就是一次贪心偿试，之后还进行过两次调整，但都失败了，昨天终于放弃了这个念头，开始从动态规划的角度分析这个题目，构造了上面的算法。在分析算法复杂度的时候意外推导出一个数列公式，呵呵，意外的收获。

卖个关子，也许你早就知道，但这里还是先描述一下这个数列
设
s(n) = 1 + 2 + 3 + ... + n
v(n) = s(1) + s(2) + s(3) + ... + s(n)
计算v(n)

谈谈你的想法，有兴趣的话我再开个英雄贴送分

我姓曹，叫我小曹好了，今年大二，不过我不是计算机专业的，学这个只是兴趣，下学期报了计算机二专，可以系统得学习了

这题我没想到很精妙的方法，只能硬算：

首先由
(n+1)^3-n^3==3*n*n+3*n+1
n^3-(n-1)^3==3*(n-1)*(n-1)+3*(n-1)+1
.
.
.
2^3-1^3==3*1*1+3*1+1

上面n个式子相加，可以得到公式:1^2+2^2+3^2.......n^2==1/6*n*(n+1)*(2n+1)

然后上面直接得到公式=1/2*SUM(k^2+k)   (1<=k<=n)

将上面那个公式套进去，最后结果应该是1/6*n*(n+1)*(n+2)

今天晚上再想想看有没有巧妙一点的方法吧