最大的算式

P1045 最大的算式

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

题目很简单，给出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

输出

120

备注

对于30%的数据，N<= 10；
对于全部的数据，N <= 100。

//define几乎就是高级替换，写一些简单的函数还是比较资磁的，于是搞了个求和的

于是木有乘号的时候直接全部求和就好啦，加之间看成区间求和

另外乘号和加号一共就是N-1个所以循环的次数你懂得

那返回值自然显而易见了

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define inf 0x7fffffff
 6 using namespace std;
 7 int n,k;
 8 int a,sum[105];
 9 int dp[105][105][105];
10 #define sigma(i,j)(sum[j]-sum[(i)-1])
11 int dfs(int i,int j,int k)
12 {
13     if(i==j&&k==0)return sigma(i,i);
14     if(dp[i][j][k]!=-1)return dp[i][j][k];
15     if (k == 0) return sigma(i,j);
16     dp[i][j][k] = 0;
17     for (int p = i; p < j; p++)
18         dp[i][j][k] = max (dp[i][j][k], sigma(i,p)*dfs(p+1,j,k-1));
19     return dp[i][j][k];
20 }
21 int main()
22 {
23     scanf("%d%d",&n,&k);
24     memset(sum,0,sizeof(sum));
25     for(int i=1;i<=n;i++)
26     {
27         scanf("%d",&a);
28         sum[i]=sum[i-1]+a;
29     }
30     memset(dp,-1,sizeof(dp));
31     cout<<dfs(1,n,k);
32     puts("");
33     return 0;
34 }

QAQ

//智障的读入忘记加地址符了然后调了好久

//数组别开销了，n的范围是100