【Tyvj1045】最大的算式

2014-03-27
竞赛题解 / 动态规划
TYVJ

描述 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。

Tyvj 1045

代码 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;
}