P1018 10pts AC#1#14 蒟蒻求助
查看原帖
P1018 10pts AC#1#14 蒟蒻求助
1126325
Indestructible楼主2024/6/18 19:43
#include<bits/stdc++.h>
const int maxn=42,maxm=7;
int n,k;
char st[maxn];
struct Int{
	int a[maxn],size;
	void input(){
		std::string s;
		std::cin>>s;
		size=s.size();
		for (int i=0;i<size;i++){
			a[size-i-1]=s[i]-'0';
		}
	}
	void print(){
		for (int i=size-1;i>=0;i--){
			printf("%d",a[i]);
		}
		printf("\n");
	}
	void clear(){
		memset(a,0,sizeof(a));
		size=0;
	}
	void setnum(int n){
		clear();
		for (;n;size++,n/=10) a[size]=n%10;
	}
};
Int dp[maxn][maxm];
Int max(Int x,Int y){
	int x1=x.size,y1=y.size;
	if (x1!=y1) return x1>y1?x:y;
	for (int i=x1-1;i>=0;i--){
		if (x.a[i]!=y.a[i]) return x.a[i]>y.a[i]?x:y;
	}
	return x;
} 
Int change(Int x,int n){
	for (int i=x.size;i>=1;i--) x.a[i]=x.a[i-1];
	x.size++,x.a[0]=n; return x;
}
Int mul(Int x,int l,int r){
	Int y,s; s.clear(),y.clear();
	for (int i=l;i<=r;i++) y.a[r-i]=st[i]-'0';
	for (int i=0;i<x.size;i++) for (int j=0;j<r-l+1;j++)
		s.a[i+j]+=x.a[i]*y.a[j],s.a[i+1]+=s.a[i]/10,s.a[i]%=10;
	s.size=s.a[x.size+r-l]?x.size+r-l+1:x.size+r-l;
	return s;
}
signed main(){
	scanf("%d%d%s",&n,&k,st+1);
	for (int i=1;i<=n;i++) dp[i][0]=change(dp[i-1][0],st[i]-'0');
	for (int i=1;i<=n;i++) for (int j=1;j<=std::min(i,k);j++) for (int l=j;l<=i;l++)
		dp[i][j]=max(dp[i][j],mul(dp[l][j-1],l+1,i));
	dp[n][k].print();
	return 0;
}
2024/6/18 19:43
加载中...