描述 Description
题目很简单,给出 N 个数字,不改变它们的相对位置,在中间加入 K 个乘号和 N-K-1 个加号,(括号随便加)使最终结果尽量大。因为乘号和加号一共就是 N-1 个了,所以恰好每两个相邻数字之间都有一个符号。例如:
N=5, K=2,5 个数字分别为 1、2、3、4、5,可以加成:
12(3+4+5)=24
1(2+3)(4+5)=45
(12+3)(4+5)=45
……
输入格式 InputFormat
第一行为两个有空格隔开的整数,表示 N 和 K,其中 (2<=N<=15, 0<=K<=N-1)。
第二行为 N 个用空格隔开的数字(每个数字在 0 到 9 之间)。
输出格式 OutputFormat
输出文件仅一行包含一个整数,表示要求的最大的结果。
最后的结果 <=maxlongint。
样例输入 SampleInput
5 2
1 2 3 4 5
样例输出 SampleOutput
120
注释 Hint
对于 30% 的数据,N<=10;
对于全部的数据,N<=100。
代码 Code
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f[101][101];
int sum[101];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
for (i=1;i<=n;i++)
{
scanf("%d",&t);
sum[i]=sum[i-1]+t;
f[i][0]=sum[i];
}
for (i=1;i<=n;i++) for (j=1;j<=min(m,i-1);j++) for (k=1;k<i;k++)
{
f[i][j]=max(f[i][j],f[k][j-1]*(sum[i]-sum[k]));
}
printf("%d\n",f[n][m]);
return 0;
}