题意：即求给定n个数字(a1,a2,……an)，不改变序列，分成M份，使每一份和的乘积最大。
思路：dp[i][j]表示把前i个数字，分成j份所能得到的最大乘积。
转移方程：dp[i][j] = max{ dp[k][i-1]*sum(k+1,j) } 其中显然j<=i(分成j份，至少要有i个数才能分)且i-1<=k<j
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10007 int a[],dp[][],sum[]; int SUM(int l,int r)
{
return sum[r]-sum[l-];
} int main()
{
int t,i,n,m,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
sum[] = ;
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i] = sum[i-] + a[i];
}
for(i=;i<=;i++)
{
for(j=;j<=i;j++)
dp[i][j] = ;
for(j=i+;j<=;j++)
dp[i][j] = ;
}
for(i=;i<=n;i++)
{
int s = ;
for(j=;j<=i;j++)
s *= a[j];
dp[i][i] = s;
}
for(i=;i<=n;i++)
{
for(j=;j<=i;j++)
{
int maxi = -;
for(k=j-;k<i;k++)
{
maxi = max(maxi,dp[k][j-]*SUM(k+,i));
}
dp[i][j] = max(maxi,dp[i][j]);
}
}
printf("%d\n",dp[n][m]);
}
return ;
}