华师一附中OI组

标题: 最大的算式 [打印本页]
作者: admin    时间: 2018-6-3 11:42
标题: 最大的算式
给出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之间）。

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

样例
BIGEXP.IN
5 2
1 2 3 4 5

BIGEXP.OUT
120

说明
(1+2+3)*4*5=120
作者: 黄煦喆    时间: 2018-7-29 16:42
  1. #include<iostream>
  2. using namespace std;
  3. int n,k,a[20],dp[20][20],s[20];
  4. int i,j,v;
  5. int main()
  6. {
  7.     cin>>n>>k;
  8.     for (int i=1; i<=n; i++)
  9.     {
  10.         cin>>a[i];
  11.         s[i]=s[i-1]+a[i];
  12.         dp[i][0]=s[i];
  13.     }
  14.     for (i=2; i<=n; i++)
  15.     {
  16.         int t=min(i-1,k);
  17.             for (j=1;j<=t;j++)
  18.                 for (v=2;v<=i;v++)
  19.                     dp[i][j]=max(dp[i][j],dp[v-1][j-1]*(s[i]-s[v-1]));
  20.     }
  21.     cout<<dp[n][k]<<endl;
  22.     return 0;
  23. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2