题目描述
给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：
N=5, K=2，5个数字分别为1、2、3、4、5，可以加成：
1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
……
输入输出格式
输入格式：
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中(2<=N<=15, 0<=K<=N-1)。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。
输出格式：
输出文件仅一行包含一个整数，表示要求的最大的结果
最后的结果<=maxlongint
输入输出样例
输入样例#1： 复制
5 2
1 2 3 4 5
输出样例#1： 复制
120 -----------------------------------------------------------------------------
分析：一开始想用dp[i][j]表示i到j个数的最大值，可发现无论在循环上限还是其他地方都用不上k，然后我就看了题解这么想：在这题中，可以用dp[i][j]表示在前i个数中插入j个乘号。我们可以先处理前缀和，将dp[i][0]设为从a[1]加到a[i]的值，接着跑一个循环，寻找位置，插入一个乘号。就这样递推就可以得出答案了。
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[][],a[];
int main()
{
int x,n,k;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d",&x);
a[i]=a[i-]+x;//前缀和
dp[i][]=a[i];
}
for(int i=;i<=n;i++)
for(int j=;j<=min(k,i-);j++)
{
for(int k=;k<=i;k++)
dp[i][j]=max(dp[i][j],dp[k][j-]*(a[i]-a[k]));
}
printf("%d",dp[n][k]);
return ;
}