WA on #11 #12 #13 求调
查看原帖
WA on #11 #12 #13 求调
1162628
Lanpinye_Only楼主2024/8/7 21:26
#include<bits/stdc++.h>
#define N 500005
#define MAX N*2
using namespace std;
string dp[64][9];
string s;
int n,m;
string num(int l,int r){
	string sum="";
	for(int i=l;i<=r;i++){
		sum+=s[i];
	}
	return sum;
}
string mul(string m,string n){
	int a[N]={0},b[N]={0},c[MAX]={0};
	int len_m=m.size();
	int len_n=n.size();
	for(int i=0;i<len_m;i++)a[i]=m[len_m-i-1]-'0';
	for(int i=0;i<len_n;i++)b[i]=n[len_n-i-1]-'0';
	for(int i=0;i<len_m;i++)
		for(int j=0;j<len_n;j++)
			c[i+j]+=a[i]*b[j];
	int ans_len=0;
	for(int i=0;i<len_m+len_n;i++){
		c[i+1]+=c[i]/10;
		c[i]%=10;
		ans_len++;
	}
	while(!c[ans_len])ans_len--;
	string ans;
	for(int i=ans_len;i>=0;i--){
		ans+=c[i]+'0';
	}
	return ans;
}
string max_(string a,string b){
	if(a.size()>b.size())return a;
	else if(a.size()<b.size())return b;
	else{
		for(int i=0;i<a.size();i++){
			if(a[i]==b[i])continue;
			else if(a[i]-'0'>b[i]-'0')return a;
			else return b;
		}
	}
}
int main(){
	cin>>n>>m;
	cin>>s;
	s=" "+s;
	for(int i=1;i<=n;i++){
		dp[i][0]=num(1,i);
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=min(i-1,m);j++){
			for(int k=j;k<i;k++){
				dp[i][j]=max_(dp[i][j],mul(dp[k][j-1],num(k+1,i)));
			}
		}
	}
	cout<<dp[n][m];
}
2024/8/7 21:26
加载中...