P1018 maximum product solution

P1018 Product maximum

The question ： There's a string s(|s|<=40), to k(k<=6) A multiple sign , Ask how to combine to get the largest number .

solution ： This question is not difficult ！ It's just too complicated ！40 Bit data , Can only use high precision , It is dp, Preprocess first qj[i][j] (i≤j) Express s The string position is i-j The string of ,dp[i][j] Said to i For the end j The largest number obtained by a multiplication sign , So the transfer equation is $dp[i][j]=max(dp[i][j],dp[x][j-1]\ast qj[x+1][i])$, Just pay attention to the boundary problem .

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int ne[4][2] = {
    1, 0, 0, 1, -1, 0, 0, -1};
const int N = 50;
int n, k;
string s;

string max(string a, string b) {
    
	if(a.size() != b.size()) return a.size() < b.size() ? b : a; 
	return a < b ? b : a; 
}

// High precision addition  
string add(string a, string b) {
    
	string res = "", r = "";
	int jw = 0, l1 = a.size(), l2 = b.size();
	int p1 = l1-1, p2 = l2-1, mid;
	while(p1 >= 0 && p2 >= 0) {
    
		mid = a[p1--]-'0'+b[p2--]-'0'+jw; jw = 0;
		r = (mid%10)+'0';
		res.insert(0, r);
		if(mid >= 10) jw = mid/10;
	}
	while(p1 >= 0) {
    
		mid = a[p1--]-'0'+jw; jw = 0;
		r = (mid%10)+'0';
		res.insert(0, r);
		if(mid >= 10) jw = mid/10;
	}
	while(p2 >= 0) {
    
		mid = b[p2--]-'0'+jw; jw = 0;
		r = (mid%10)+'0';
		res.insert(0, r);
		if(mid >= 10) jw = mid/10;
	}
	if(jw) res.insert(0, "1");
	return res;
}

// High precision multiplication 
string mul(string a, string b) {
    
	string res = "", r1 = "", r;
	int jw = 0, l1 = a.size(), l2 = b.size();
	int mid, num_0 = 0;
	for(int i = l2-1; i >= 0; --i) {
    
		r1 = "";
		for(int j = l1-1; j >= 0; --j) {
    
			mid = (b[i]-'0')*(a[j]-'0')+jw; jw = 0;
			r = (mid%10) + '0';
			r1.insert(0, r);
			if(mid >= 10) jw = mid / 10;
		}
		if(jw) {
     r = jw + '0', r1.insert(0, r); jw = 0; }
		for(int j = 0; j < num_0; ++j) r1.append("0");
		++num_0;
		res = add(res, r1); 
	}
	return res;
} 

string qj[N][N], dp[N][N];
int main() {
    
	cin >> n >> k >> s;
	int len = s.size();
	for(int i = 0; i < len; ++i) for(int j = i; j < len; ++j) 
		qj[i][j] = s.substr(i, j-i+1);
	// Preprocessing 
	for(int i = 0; i < len; ++i) {
    
		dp[i][0] = qj[0][i];
		for(int j = 1; j <= k; ++j) dp[i][j] = "0";
	}
	//dp!
	for(int i = 0; i < len; ++i) {
    
		for(int j = 1; j <= k; ++j) {
    
			for(int x = j-1; x < len; ++x) {
    
				dp[i][j] = max(dp[i][j], mul(dp[x][j-1], qj[x+1][i]));
			}
		}
	}
	cout << dp[len-1][k] << endl;
	return 0;
}