看这个n<=15本以为是个状压DP
还是too young
这个题最神奇的地方是加括号是根据贪心的策略。
发现只有在一连串的加号两边加上括号才是最优的（想一想，为什么？）
f[i][j]表示前i个数加j个乘号的最优解
#include <cstdio>
#define max(x, y) ((x) > (y) ? (x) : (y))
int n, m;
int f[20][20];
int main()
{
int i, j, k, x;
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++)
{
scanf("%d", &x);
f[i][0] = f[i - 1][0] + x;
}
for(i = 2; i <= n; i++)
for(j = 1; j < i; j++)
for(k = 1; k < i; k++)
f[i][j] = max(f[i][j], f[k][j - 1] * (f[i][0] - f[k][0]));
printf("%d\n", f[n][m]);
return 0;
}
原文：http://www.cnblogs.com/zhenghaotian/p/7301276.html