[NOIP2000 提高组]-乘积最大：隔板法-DFS搜索

[NOIP2000 提高组] 乘积最大

题目描述

今年是国际数学联盟确定的“ 2000 ――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为 $N$ 的数字串，要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分，找出一种分法，使得这 $K+1$ 个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：$312$， 当 $N=3,K=1$ 时会有以下两种分法：

1. $3\times 12=36$
2. $31\times 2=62$

这时，符合题目要求的结果是: $31\times 2=62$

现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。

输入格式

程序的输入共有两行：

第一行共有 $2$ 个自然数 $N,K$（$6\le N\le 40,1\le K\le 6$）

第二行是一个长度为 $N$ 的数字串。

输出格式

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

样例 #1

样例输入 #1

4  2
1231
1
2

样例输出 #1

62
1

组合数学-隔板法

插空法，数学术语，是用来解决某些元素不相邻的排列组合题，即不邻问题。如果最左最右不能插入只能在中间插入，也可叫做隔板法。

对于一个长度为n数字字符串，有n-1个空隙可以插入乘号。这个可以看做是在n-1个空隙中插入k(k<=n-1)个板的组合问题。具体有多少种组合方案可以通过DFS搜索得到。而组合方案数目为:$C_{n-1}^k$

解题思路

• 先要得到所有插入乘号的具体方案。这里使用DFS搜索实现。
• 其次用枚举遍历所有插入方案，计算方案对应的乘积。求出最值。
• 这里要注意数字的长度最多40，所以要用高精度大数相除。

具体代码

package main

import (
	"fmt"
	"strconv"
)

var n, k int
var ans = make([][]int, 0)	// 储存总方案
var temp = make([]int, 0)	// 临时方案

// DFS搜索隔板方案
func DFS(x int) {
	if x >= n {
		return
	}
	if len(temp) == k {
		tempcp := make([]int, k)
		copy(tempcp, temp)
		ans = append(ans, tempcp)
		return
	}
	for i := x; i < n-1; i++ {
		temp = append(temp, i)
		DFS(i + 1)
		temp = temp[0 : len(temp)-1]
	}
}

// 求乘积
func mult(s string, spl []int) string {
	res, now := "1", 0
	for i := 0; i < len(spl); i++ {
		num := s[now : spl[i]+1]
		res = times(res, num)
		now = spl[i] + 1
	}
	num := s[now:n]
	res = times(res, num)
	return res
}

// 大数相除
func times(s1, s2 string) string {
	if s1 == "0" || s2 == "0" {
		return "0"
	}
	res := ""
	l1, l2 := len(s1), len(s2)
	num1, num2, num3 := make([]int, l1), make([]int, l2), make([]int, l1+l2)
	for i := 0; i < l1; i++ {
		num1[i] = int(s1[l1-i-1] - '0')
	}
	for i := 0; i < l2; i++ {
		num2[i] = int(s2[l2-i-1] - '0')
	}
	for i := 0; i < l1; i++ {
		for j := 0; j < l2; j++ {
			num3[i+j] += num1[i] * num2[j]
			num3[i+j+1] += num3[i+j] / 10
			num3[i+j] %= 10
		}
	}
	if num3[l1+l2-1] != 0 {
		res += strconv.Itoa(num3[l1+l2-1])
	}
	for i := l1 + l2 - 2; i >= 0; i-- {
		res += strconv.Itoa(num3[i])
	}
	return res
}

func max(a, b string) string {
	l1, l2 := len(a), len(b)
	if l1 > l2 {
		return a
	} else if l1 < l2 {
		return b
	} else {
		if a > b {
			return a
		}
		return b
	}
}

func main() {
	var s string
	res := "0"
	fmt.Scan(&n, &k)
	fmt.Scan(&s)
	DFS(0)
	for i := 0; i < len(ans); i++ {
		res = max(res, mult(s, ans[i]))
	}
	fmt.Println(res)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98