题解：乘积最大

• 题目
  • 题目描述
  • 输入格式
  • 输出格式
  • 输入输出样例
    • 输入
    • 输出
• 解析
  • 注意几个地方
    • 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
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;
}