算法训练最大的算式

r囧r小猫 2022-03-12 10:08 157阅读 0赞

问题描述

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

输出格式

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

样例输入

5 2  
1 2 3 4 5

样例输出

120

样例说明

(1+2+3)\*4\*5=120

要注意总和可能超出int范围。

主要还是枚举最后一次乘法，把式子拆成两部分。

#include<bits/stdc++.h>
    using namespace std;
    
    long long int dp[21][21];
    int a[21];
    
    int main()
    {
        int n,k;
        cin>>n>>k;
        int ans=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            ans+=a[i];
            dp[i][0]=ans;
        }
        for(int i=1;i<=n;i++){
            int len=min(i-1,k);
            for(int j=1;j<=len;j++){
                for(int t=2;t<=i;t++){
                    dp[i][j]=max(dp[i][j],dp[t-1][j-1]*(dp[i][0]-dp[t-1][0]));
                }
            }
        }
        cout<<dp[n][k]<<endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java结合GIS训练算法实现最大熵

[资源下载地址][Link 1]：https://download.csdn.net/download/sheziqiong/88284338 [资源下载地址][Link

末蓝、/ 2024年03月26日 22:30/ 0 赞/ 33 阅读

相关蓝桥杯算法训练最大最小公倍数（贪心）

算法训练最大最小公倍数时间限制：1.0s 内存限制：256.0MB 问题描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式

悠悠/ 2024年02月17日 20:39/ 0 赞/ 58 阅读

相关【蓝桥杯】ALGO-116 最大的算式动态规划资源分配类型（最大乘积）

资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随

r囧r小猫/ 2022年12月07日 15:24/ 0 赞/ 126 阅读

相关算法训练最大最小公倍数

> 问题描述 > 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。 > 输入格式 > 输入一个正整数N。 > 输出格式 > 输出

墨蓝/ 2022年09月29日 04:09/ 0 赞/ 18 阅读

相关 ♥蓝桥杯 ALGO-116 最大的算式

算法训练最大的算式时间限制：1.0s 内存限制：256.0MB 问题描述　　题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（

比眉伴天荒/ 2022年08月19日 11:13/ 0 赞/ 196 阅读

相关蓝桥杯算法训练（二）最大最小公倍数 C语言

最大最小公倍数 C语言问题描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一

傷城~/ 2022年03月21日 14:20/ 0 赞/ 286 阅读

相关算法训练最大的算式

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

r囧r小猫/ 2022年03月12日 10:08/ 0 赞/ 158 阅读

相关算法训练最大最小公倍数

问题描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最小公倍数。

骑猪看日落/ 2022年03月09日 09:30/ 0 赞/ 227 阅读

相关算法训练最大最小公倍数

问题描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最小公

Love The Way You Lie/ 2022年03月01日 11:39/ 0 赞/ 212 阅读

相关试题算法训练大等于n的最小完全平方数

资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　输出大等于n的最小的完全平方数。　　若一个数能表示成某个自然数的平方的形式，则称这个数为

深藏阁楼爱情的钟/ 2021年09月24日 00:24/ 0 赞/ 270 阅读