P1249 最大乘积

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 \(3=1+2\)，\(4=1+3\)，\(5＝1+4=2+3\)，\(6=1+5＝2+4\)。

现在你的任务是将指定的正整数 \(n\) 分解成若干个互不相同的自然数（也可以不分解，就是这个数字本身）的和，且使这些自然数的乘积最大。

输入格式

只一个正整数 \(n\)，（\(3 \leq n \leq 10000\)）。

输出格式

第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

样例

输入样例 #1

10

输出样例 #1

2 3 5
30

解题思路

这里取自 离散小波变换° 的动态规划解法。

题目描述中“一个正整数一般可以分为几个互不相同的自然数的和”，也就是将自然数 \(n\) 拆解为若干个互不相同的数进行乘法运算得到最大的分解方案，输出分解方案及乘积结果。

那么将其视为 \(01\) 背包问题，即从 \(1\) 到 \(n\) 中选择若干数使其和为 \(n\) 且乘积最大，但是背包问题中的价值是进行加法运算得到的，这是我们需要将乘积转换为加法运算，对数中有一个很好的性质，即 \(lna+lnb=ln(ab)\)，因此我们取每个数的对数为价值，而体积为数本身，在转移过程中记录方案，最后根据方案进行大数乘小数的高精度运算。

C++代码

#include <bits/stdc++.h>
#include <sstream>
using namespace std;
const int N = 10010;
typedef long long LL;

vector<int> mul(vector<int> A, int B) {
	vector<int> C;
	int t = 0;
	for (int i = 0; i < A.size() || t; i++) {
		if (i < A.size())
			t += A[i] * B;
		C.push_back(t % 10);
		t /= 10;
	}
	while (C.size() > 1 && C.back() == 0)
		C.pop_back();
	return C;
}

vector<int> intToVector(int x) { // x > 0
	vector<int> X;
	while (x) {
		X.push_back(x % 10);
		x /= 10;
	}
	return X;
}

int n;
double f[N], v[N]; // v 为价值
int w[N], path[N]; // path 存储路径
vector<int> ans; // 存储最终方案

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) { // 初始化
		w[i] = i;
		v[i] = log(i);
	}
	for (int i = 1; i <= n; i++)
		for (int j = n; j >= i; j--) {
			if (f[j - w[i]] + v[i] > f[j]) { // 滚动数组
				f[j] = f[j - w[i]] + v[i];
				path[j] = j - w[i];
			}
		}
	for (int i = n; i; i = path[i])
		ans.push_back(i - path[i]);
	sort(ans.begin(), ans.end());
	vector<int> res;
	res.push_back(1);
	for (int i = 0; i < ans.size(); i++) {
		res = mul(res, ans[i]);
		cout << ans[i] << ' ';
	}
	cout << endl;
	for (int i = res.size() - 1; i >= 0; i--)
		cout << res[i];
	return 0;
}