• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

题解:乘积最大

开发技术 开发技术 4天前 6次浏览

目录
  • 题目
    • 题目描述
    • 输入格式
    • 输出格式
    • 输入输出样例
      • 输入
      • 输出
  • 解析
    • 注意几个地方
      • 1、计算
      • 2、状态转移方程
      • 3、边界条件
      • 4、高精度
  • 代码

题目

题目描述

今年是国际数学联盟确定的“ 2000 ――世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:
有一个数字串:312, 当 N=3,K=1时会有以下两种分法:

3×12=36 
31×2=62 

这时,符合题目要求的结果是: 31×2=62
现在,请你帮助你的好朋友 XZ 设计一个程序,求得正确的答案。

输入格式

程序的输入共有两行:
第一行共有2个自然数 N,K(6≤N≤40,1≤K≤6)
第二行是一个长度为N的数字串。

输出格式

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

输入输出样例

输入
4  2
1231
输出
62

解析

记忆化搜索,dfs(x,y),x表示第一个乘号出现的位置,y表示还剩多少个乘号。

注意几个地方

1、计算
long long sum(long long x,long long y) {
    long long ans = 0;
    for(int i = x; i <= y; i++) {
	    ans = ans * 10;
	    ans = ans + a[i];
    }
    return ans;
}

这个用于计算分出来的段组成的数的值,注意一定要先乘十再累加

2、状态转移方程
for(int i = x + 1; i  <= N; i++) {
	    ans = max(ans,dfs(i,y - 1) * sum(x,i - 1));
    }

枚举乘号位置,后面继续搜,前面算数

3、边界条件
if(dp[x][y]) return dp[x][y];//已经搜过了
if(N - x < y) return 0;//乘号比数多
if(y == 0) return sum(x,N);//乘号用完了
4、高精度

正常来说,这道题需要使用高精,但是重在思路,所以我并没有花时间去写。。

代码

#include<bits/stdc++.h>
using namespace std;
int N,K;
long long a[10001];
long long dp[101][1001];
long long sum(long long x,long long y) {
    long long ans = 0;
    for(int i = x; i <= y; i++) {
	    ans = ans * 10;
	    ans = ans + a[i];
    }
    return ans;
}
long long dfs(int x,int y) {
    long long ans = 0;
    if(dp[x][y]) return dp[x][y];
    if(N - x < y) return 0;
    if(y == 0) return sum(x,N);
    for(int i = x + 1; i  <= N; i++) {
	    ans = max(ans,dfs(i,y - 1) * sum(x,i - 1));
    }
    return dp[x][y] = ans;
}
int main() {
    scanf("%d %d" ,&N,&K);
    for(int i = 1; i <= N; i++) {
	    scanf("%1lld" ,&a[i]);
    }
    printf("%lld" ,dfs(1,K));
    return 0;
}

程序员灯塔
转载请注明原文链接:题解:乘积最大
喜欢 (0)