样例没过求条
查看原帖
样例没过求条
1059234
Ybw0731楼主2025/7/1 22:05
#include<bits/stdc++.h>
//#define int long long
#define PII pair<int,int>
#define endl "\n"
using namespace std;
const int N=45;
const int INF=0x3f3f3f3f3f3f3f3f;
const double EPS=1e-6;
const int MOD=1e9+7;
class BINT{
private:
	string s;
public:
	BINT(string x="0"):s(x){};
	const BINT operator+(const BINT&t){
		string sa=s,sb=t.s;
		int la=sa.size(),lb=sb.size();
		int m=max(la,lb);
		vector<int>a(m+1,0),b(m+1,0),c(m+1,0);
		for(int i=0;i<la;i++)a[i]=sa[la-1-i]-'0';
		for(int i=0;i<lb;i++)b[i]=sb[lb-1-i]-'0';
		for(int i=0;i<m;i++){
			c[i]+=a[i]+b[i];
			c[i+1]+=c[i]/10;
			c[i]=c[i]%10;
		}
		while(!c[m]&&m)m--;
		string res;
		for(int i=m;i>=0;i--)res+=char(c[i]+'0');
		return BINT(res);
	}
	const BINT operator*(const BINT&t){
		string sa=s,sb=t.s;
		int la=sa.size(),lb=sb.size();
		int m=la+lb;
		vector<int>a(m+1,0),b(m+1,0),c(m+1,0);
		for(int i=0;i<la;i++)a[i]=sa[la-1-i]-'0';
		for(int i=0;i<lb;i++)b[i]=sb[lb-1-i]-'0';
		for(int i=0;i<la;i++){
			for(int j=0;j<lb;j++){
				c[i+j]+=a[i]*b[j];
				c[i+j+1]+=c[i+j]/10;
				c[i+j]%=10;
			}
		}
		while(!c[m]&&m)m--;
		string res;
		for(int i=m;i>=0;i--)res+=char(c[i]+'0');
		return BINT(res);
	}
	bool operator<(const BINT&t){
 		string b=t.s;
		if(s.size()<b.size())return 1;
		if(s.size()==b.size()&&s<b)return 1;
		return 0;
	}
	void operator=(const string&x){
		s=x;
	}
	void operator=(const long long&x){
		s=to_string(x);
	}
	void operator=(const int&x){		
		s=to_string(x);
	}
	friend istream&operator>>(istream&in,BINT&t){
		in>>t.s;
		return in;
	}
	friend ostream&operator<<(ostream&out,const BINT&t){
		out<<t.s;
		return out;
	}
};
int n,m;
string s;
BINT dp[N][N],f[N][N];
void solve(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			f[i][j]=s.substr(i,j-i+1);
		}
	}
	for(int i=1;i<=n;i++)dp[i][0]=f[1][i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			for(int k=j;k<i;k++){
				if(dp[i][j]<dp[k][j-1]*f[k+1][i])dp[i][j]=dp[k][j-1]*f[k+1][i];
			}
		}
	}
	cout<<dp[n][m];
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T=1;
//	cin>>T;
	while(T--)solve();
	return 0;
}
2025/7/1 22:05
加载中...