Algorithm Notebook 4

P1249最大乘积

题意：给出一个大自然数n，分解为一系列自然数的和，求其最大值。

思路：在纸上手动分解之后会发现，当数小于4时，分解没有意义；当数更大的时候，可以先从2开始慢慢分解，
到分解到无法继续分解，还有剩的时候，可以将剩下的数从最大数往最小的数加上去，加完了还有剩，再从最大的地方加。

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN = 1000 + 5;

struct Bigint{
	int len;
	int a[MAXN];

	Bigint(int x = 0){
		memset(a, 0, sizeof(a));
		for (len = 1; x; len++){
			a[len] = x % 10;
			x /= 10;
		}
		len--;
	}
	int &operator[](int i) {return a[i];}

	void flatten(int L){
		len = L;
		for (int i = 1; i <= len; i++){
			a[i + 1] += a[i] / 10;
			a[i] = a[i] % 10;
		}
		while(!a[len])
			len--;
	}

	Bigint operator*(int b) const{
		Bigint c;
		for (int i = 1; i <= len; i++)
			c[i] = a[i] * b;
		c.flatten(len + to_string(b).length());
		return c;
	}

	void print(){
		for (int i = len; i >= 1; i--){
			cout << a[i];
		}
	}
};

int main(){
	int n;
	cin >> n;

	vector <int> q;
	int sum = 0;
	if (n >= 4){ 
		for (int i = 2; i + sum <= n; i++){
			q.push_back(i);
			sum += i;
		}
		int p = q.size() - 1;
		int t = n - sum;
		while (t){
			if (p == -1) p = q.size() - 1;
			q[p]++;
			p--;
			t--;
		}
		for (auto tmp : q) cout << tmp << " ";
		cout << "\n";

		Bigint ans(1);
		for (auto tmp : q){
			ans = ans * tmp;
		}
		ans.print();
	}
	else cout << n;
	return 0;
}

总结：

• 1.当看到题没有思路的时候，可以找几个特例，寻找规律
• 2.不需要执着于数学上的最优解与证明，可以先找到一个可行解，之后再优化

坑点：

• 1.当n小于4时，分解没有意义，直接输出n
• 2.有可能会遇到无法分解的情况，剩下的部分要往回加