华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1560|回复: 1
打印 上一主题 下一主题

最大的算式

[复制链接]

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
跳转到指定楼层
楼主
发表于 2018-6-3 11:42:10 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
给出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
回复

使用道具 举报

9

主题

158

帖子

470

积分

华一学生

积分
470
QQ
沙发
发表于 2018-7-29 16:42:03 | 只看该作者
  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. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-11-2 12:35 , Processed in 0.098968 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表