乘积最大

P1018 乘积最大,P1018乘积

标题陈诉

现年是国际数学生联合会盟鲜明的“3000――世界数学年”,又恰逢本国有名物军事学家Loo-keng Hua先生寿辰90周年。在Loo-keng Hua先生的故乡广西金坛,协会了一场改头换面包车型地铁数学智力竞技的运动,你的叁个好相恋的人XZ也可能有幸得以参与。活动中,主持人给持有加入运动的运动员出了这么一道标题:

存在八个尺寸为N的数字串,供给选手采取K个乘号将它分为K+1个部分,搜索一种分法,使得那K+1个部分的乘积可感到最大。

并且,为了辅辅助选举手能够正确驾驭题意,主持人还举了之类的二个事例:

有二个数字串:312, 当N=3,K=1时会有以下二种分法:

1) 3*12=36

2) 31*2=62

此刻,符合标题须要的结果是:31*2=62

今昔,请你帮忙您的好对象XZ设计一个程序,求得正确的答案。

始发定义状态f[i][j][乘积最大。k]为[i,j)区间插入k个括号,使用纪念化寻找,不过成功爆栈,得到4个mle

标题陈诉

今年是国际数学生联合会盟鲜明的“两千――世界数学年”,又恰逢本国著名科学家Loo-keng Hua先生寿辰90周年。在Loo-keng Hua先生的家门广西金坛,协会了一场面目一新包车型大巴数学智力比赛的运动,你的三个好相恋的人XZ也可以有幸得以插手。活动中,主持人给具有在座运动的选手出了那般一道标题:

存在八个长度为N的数字串,供给选手接纳K个乘号将它分成K+1个部分,找寻一种分法,使得那K+1个部分的乘积能够为最大。

与此同一时间,为了援救选手能够准确明白题意,主持人还举了如下的两个例证:

有三个数字串:312, 当N=3,K=1时会有以下三种分法:

1) 3*12=36

2) 31*2=62

那儿,符合标题要求的结果是:31*2=62

近些日子,请你补助您的好恋人XZ设计三个前后相继,求得正确的答案。

题目汇报

当年是国际数学缔盟分明的“3000――世界数学年”,又恰逢本国盛名物历史学家Loo-keng Hua先生出生之日90周年。在Loo-keng Hua先生的故里多瑙河金坛,组织了一场万象更新包车型客车数学智力竞技的运动,你的三个好恋人XZ也可能有幸得以参加。活动中,主持人给持有在座运动的运动员出了那般一道标题:

存在三个长短为N的数字串,供给选手选取K个乘号将它分为K+1个部分,寻找一种分法,使得那K+1个部分的乘积可以为最大。

并且,为了扶持选手能够正确驾驭题意,主持人还举了如下的四个例证:

有一个数字串:312, 当N=3,K=1时会有以下二种分法:

1) 3*12=36

2) 31*2=62

这会儿,符合标题供给的结果是:31*2=62

今昔,请你支持你的好对象XZ设计一个程序,求得精确的答案。

输入输出格式

输入格式:

前后相继的输入共有两行:

先是行共有2个自然数N,K(6≤N≤40,1≤K≤6)

第二行是二个尺寸为N的数字串。

输出格式:

结果彰显在显示屏上,相对于输入,应输出所求得的最大乘积。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 45;
int n, k, len;
long long f[maxn][maxn][maxn];
char str[maxn];
int trans(int l, int r){
    int x = 0;
    for(int i = l; i <= r; i++) {
        x = x * 10 + str[i] - '0';
    }
    return x;
}
int dp(int left, int right, int cur) {
    if(cur <= 0) return f[left][right][cur] = trans(left, right);
    if(f[left][right][cur]) return f[left][right][cur];
    int m, ans = 0;
    for(m = left; m <= right; m++) {
        for(int c = 0; c <= cur; c++) {
            ans = max(ans, dp(left, m, c) * dp(m+1, right, cur-c));
        }
    }
    return ans;
}
int main() {
    cin >> n >> k;
    scanf("%s", str);
    len = strlen(str);
    memset(f, 0, sizeof(f));
    cout << dp(0, len-1, k);
}

输入输出格式

输入格式:

程序的输入共有两行:

先是行共有2个自然数N,K(6≤N≤40,1≤K≤6)

其次行是多个长度为N的数字串。

出口格式:

结果彰显在荧屏上,相对于输入,应输出所求得的最大乘积(贰个自然数)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注