10pts求助【玄关】
查看原帖
10pts求助【玄关】
1115392
small_moon楼主2024/10/19 16:49
#include<bits/stdc++.h>
using namespace std;
const int N=50,M=10;
int read();
int n,k;
string st;
struct Node{
	int len;
	int num[N*5];
	bool operator > (const Node &x) const
	{
		if(len>x.len) return 1;
		for(int i=len;i>=1;i--)
			if(num[i]>x.num[i]) return 1;
			else return 0;
	}
	Node operator + (const Node &x) const
	{
		Node ans; ans.len=x.len+len;
		memset(ans.num,0,sizeof ans.num);
		for(int i=1;i<=len;i++) ans.num[i]=num[i]+x.num[i];
		for(int i=1;i<=len;i++)
			if(ans.num[i]>9)
			{
				ans.num[i+1]++;
				ans.num[i]--;
			}
		while(!ans.num[ans.len]) ans.len--;
		return ans;
	}
	Node operator * (const Node &x) const
	{
		Node ans; ans.len=len+x.len;
		memset(ans.num,0,sizeof ans.num);
		for(int i=1;i<=len;i++)
			for(int j=1;j<=x.len;j++)
				ans.num[i+j-1]+=num[i]*x.num[j];
		for(int i=1;i<=ans.len;i++)
		{
			ans.num[i+1]+=ans.num[i]/10;
			ans.num[i]%=10;
		}
		while(!ans.num[ans.len]) ans.len--;
		return ans;
	}
}num[N][N],dp[N][M];
void print(Node);
Node new_node(int k)
{
	Node ans; ans.len=0;
	memset(ans.num,0,sizeof ans.num);
	while(k)
	{
		ans.len++;
		ans.num[ans.len]=k%10;
		k/=10;
	}
	return ans;
}
int main()
{
	n=read(); k=read(); cin>>st;
	for(int i=1;i<=n;i++)
	{
		num[i][i].len=1;
		num[i][i].num[1]=st[i-1]-'0';
		for(int j=i+1;j<=n;j++)
			num[i][j]=((num[i][j-1]*new_node(10))+(new_node(st[j-1]-'0')));
	}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=i;j<=n;j++) {print(num[i][j]);cout<<' ';}
//		puts(" ");
//	}
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=num[1][i];
		for(int j=1;j<=k;j++)
			for(int k=1;k<i;k++)
				if((dp[k][j-1]*num[k+1][i])>dp[i][j])
					dp[i][j]=dp[k][j-1]*num[k+1][i];
	}
	print(dp[n][k]);
	return 0;
}
int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void print(Node x)
{
	for(int i=x.len;i>=1;i--) printf("%d",x.num[i]);
}
2024/10/19 16:49
加载中...