高精求调
查看原帖
高精求调
408071
TankYu楼主2022/9/28 14:09
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;

const int maxnum = 100;

struct bigint
{
	long long x[maxnum];
	int len;
	bigint()//初始化 
	{
		assert(maxnum != 0);
		for(int i = 0;i < 100;i++)
		{
			x[i] = 0;
		}
		len = 1;
	}
	inline bigint operator + (const int b)//高加低 
	{
		bigint ans;
		for(int i = 1;i <= len;i++)
		{
			ans.x[i] = this -> x[i];
		}
		ans.len = this->len;
		ans.x[1] += b;
		for(int i = 1;i <= ans.len;i++)
		{
			if(ans.x[i] / 10 > 0 && i + 1 > ans.len)
			{
				ans.len++;
			}
			ans.x[i + 1] += ans.x[i] / 10;
			ans.x[i] %= 10;
		}
		return ans;
	}
	inline bigint operator * (const int b)//高乘低 
	{
		bigint ans;
		ans.len = this -> len;
		for(int i = 1;i <= ans.len;i++)
		{
			if(i + 1 > ans.len && x[i] * b + ans.x[i] >= 10)
			{
				ans.len++;
			}
			ans.x[i] += x[i] * b;
			ans.x[i + 1] += ans.x[i] / 10;
			ans.x[i] %= 10;
		}
		return ans;
	}
	inline bigint operator + (const bigint b)
	{
		bigint ans;
		ans.len = max(this -> len,b.len);
		for(int i = 1;i <= ans.len;i++)
		{
			ans.x[i] += (this -> x[i]) + b.x[i];
			if(ans.x[i] > 10 && i + 1 > ans.len)
			{
				ans.len++;
			}
			ans.x[i + 1] += ans.x[i] / 10;
			ans.x[i] %= 10;
		}
		return ans;
	}
	inline bigint operator * (const bigint b)
	{
		bigint ans;
		ans.len = (this -> len) + b.len;
		for(int i = 1;i <= this -> len;i++)
		{
			for(int j = 1;j <= b.len;j++)
			{
				ans.x[i + j - 1] += (this -> x[i]) * b.x[j];
			}
		}
		for(int i = 1;i <= ans.len;i++)
		{
			if(ans.x[i] >= 10 && i + 1 > ans.len)
			{
				ans.len++;
			}
			ans.x[i + 1] += ans.x[i] / 10;
			ans.x[i] %= 10;
		}
		return ans;
	}
	inline int operator < (const bigint p) const //为了方便,记得改 
	{
		for (int i = max(p.len,this -> len); i >= 1; --i) 
		{
			if (x[i] > p.x[i]) return 0;
			if (x[i] < p.x[i]) return 1;
		}
		return 0;
	}
	inline bigint operator - (const bigint b)//这个需保证减不出来负的 
	{
		bigint ans;
		for(int i = 1;i <= (this -> len);i++)
		{
			ans.x[i] = this -> x[i] - b.x[i];
			if(ans.x[i] < 0)
			{
				ans.x[i] += 10;
				ans.x[i + 1]--;
			}
		}
//		for(int i = 1;ans.x[i];i++)
//		{
//			ans.len = i;
//		}
		return ans;
	}
	void print()
	{
		int i = this -> len;
//		for(;this->x[i] == 0;i--);
		for(;i >= 1;i--)
		{
			cout << x[i];
		}
	}
} dp[50][50],ten[50],sum[50],ans;

int a[50];

int main()
{
//	bigint a;
//	a.x[1] = 1;
//	a = a * 10;
//	a.print();
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	ten[0].x[1] = 1;
	for(int i = 0;i < n;i++)
	{
		a[i + 1] = s[i] - '0';
	}
	for(int i = 1;i <= n;i++)
	{
		ten[i] = ten[i - 1] * 10;
		sum[i] = sum[i - 1] * 10 + a[i];
	}
	for(int i = 1;i < n;i++)
	{
		dp[i][1] = sum[i];
		for (int j = 2; j <= k; j++) 
		{
			for (int z = j - 1; z < i; z++)
				dp[i][j] = max (dp[i][j], dp[z][j - 1] * (sum[i] - sum[z] * ten[i - z]));
		}
		ans = max (ans, dp[i][k] * (sum[n] - sum[i] * ten[n - i]));
	}
	ans.print();
	return 0;
}

RT,这个蒟蒻可能晚上才能看帖

2022/9/28 14:09
加载中...