p1018 乘积最大

题目描述

今年是国际数学联盟确定的“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

题解

在n个数中插入k个乘号.

首先看到位数范围40位, 就能想到, 乘法操作后, 可能会爆long long, 保险起见, 上高精.

对于这个题的设定, 第i个乘号确定后将数分成的两部分, 乘号数量一定(左i-1个和右k-i个), 乘积互不影响. 所以只要保证两边单独的乘积最大, 就能保证最后的乘积最大.

这样就设计出了状态:

f(i,j)表示第j个乘号放在第i个数字之后, 前i个数字的乘积最大值.

设A[l,r]表示用A的第l位到第r位形成的高精数

那么就可以写出状态转移方程:

最后答案也可以通过f数组推出.

代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n, K, A[50], C[1005], b[50][10][1005], d[1005], ji[1005], ans[1005];
char a[50];
bool flg[1005];
void take(int l, int r) {//从A中取[l,r]区间的数字组成一个数, 存入高精数d.
	d[0] = r - l + 1;
	for (int ti = l; ti <= r; ti++) {
		d[ti - l + 1] = A[ti];
	}
	return;
}
void print(int x[]) {//打印高精数x
	for (int pi = x[0]; pi >= 1; pi--) {
		cout << x[pi];
	}
	cout << endl;
	return;
}
void times(int x[], int y[]) {//计算高精数x,y的乘积, 并且将积存入高精数ji
	memset(ji, 0, sizeof(ji));
	int xx = 0;
	for (int ti = 1; ti <= x[0]; ti++)//枚举因数A的每一位 
	{
		xx = 0;
		for (int tj = 1; tj <= y[0]; tj++) {//枚举因数B的每一位 
			ji[ti + tj - 1] += xx + (x[ti] * y[tj]);
			xx = ji[ti + tj - 1] / 10;
			ji[ti + tj - 1] %= 10;
		}
		ji[ti + y[0]] += xx;
	}
	ji[0] = x[0] + y[0];
	while (ji[ji[0]] == 0 && ji[0] > 1) {
		ji[0]--;
	}
	return;
}
bool cmp(int x[],int y[]) {//比较高精数x,y, 若x>y则返回true, 反之返回false
	if (x[0] < y[0]) {
		return false;
	}
	if (x[0] > y[0]) {
		return true;
	}
	for (int ci = x[0]; ci >= 1; ci--) {
		if (x[ci] < y[ci]) {
			return false;
		}
		if (x[ci] > y[ci]) {
			return true;
		}
	}
	return false;
}
int main() {
	cin >> n >> K;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		A[n - i + 1] = a[i] - 48;//倒着存, 高精常规操作, 不解释
	}
	A[0] = n;//高精数第0位存长度
	for (int i = 1; i < n; i++) {//枚举
		take(1, i);//这是取b[i][1]的值
		for (int ij = 0; ij <= d[0]; ij++) {//只放一个乘号, 结果固定
			b[i][1][ij] = d[ij];
		}
		for (int j = 2; j <= K; j++) {//枚举乘号
			for (int k = j; k < i; k++) {//枚举区间右界
				take(k + 1, i);//取A数的第k+1位到第i位作为一个乘数
				//print(b[k][j - 1]);//注释语句均为调试所用, 保留原因见最后一行
				times(b[k][j - 1], d);//代入第二个乘数,计算乘法
				//print(b[k][j - 1]);
				//cout << i << " " << j << endl;
				if (cmp(ji, b[i][j])) {//比较并更新(转移)
					for (int ci = 0; ci <= ji[0]; ci++) {
						b[i][j][ci] = ji[ci];
					}
				}
			}
		}
	}
	for (int i = K; i <= n - 1; i++) {//枚举放完所有的乘号后, 所得的答案
		take(i + 1, n);
		times(b[i][K], d);//乘法
		//cout << i << " " << K<< endl;
		//print(d);
		//print(b[i][K]);
		//print(ji);
		if (cmp(ji, ans)) {//比较并更新答案
			for (int j = ji[0]; j >= 0; j--) {
				ans[j] = ji[j];
			}
		}
	}
	print(ans);//输出答案
	return 0;
}//保留调试语句刚好100行

P1018 乘积最大

原文：https://www.cnblogs.com/Wild-Donkey/p/12775410.html