问题描述

　　题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：

　　N=，K=，5个数字分别为1、、、、，可以加成：

　　**(++)=

　　*(+)*(+)=

　　(*+)*(+)=

　　……

输入格式

　　输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（<=N<=, <=K<=N-）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。

输出格式

　　输出文件仅一行包含一个整数，表示要求的最大的结果

样例输入

样例输出

样例说明

　　(++)**=

 #include <stdio.h>

 #include <string.h>

 #define LEN 15

 #define MAX(X,Y) (X)>(Y)?(X):(Y)

 int main(void)

 {

     int i,j,h;

     int n,k;

     long long dp[LEN+][LEN+];    //列代表乘号个数

     memset(dp,,sizeof(dp));    

     scanf("%d%d",&n,&k);

     for (i= ; i<=n ; i++)

     {

         scanf("%d",&dp[i][]);

         dp[i][] += dp[i-][];    //乘号个数为0时

     }

     for (i= ; i<=n ; i++)    //遍历i个数

     {

         for (j= ; j<=k&&j<=i- ; j++)//乘号的个数

         {

             for (h= ; h<=i ; h ++)    //乘号的位置(第i个数的前面)

                 dp[i][j] = MAX(dp[i][j],dp[h-][j-]*(dp[i][]-dp[h-][]));

         }

     }        

     printf("%lld",dp[n][k]);

     return ;

 }