全WA,求调
查看原帖
全WA,求调
773805
wsm52楼主2024/8/24 12:55
#include<bits/stdc++.h>
using namespace std;
const int N=60;
int n,k,dp[N][N][110],a[N][N][110],tmp[110];
char s[N];
void mul(int a[],int b[]){
	memset(tmp,0,sizeof tmp);
	int i,j;
	for(i=1;i<=a[0];i++){
		int kun=0;
		for(j=1;j<=b[0];j++){
			tmp[i+j-1]+=a[i]*b[j]+kun;
			kun=tmp[i+j-1]/10;
			tmp[i+j-1]%=10;
		}
		tmp[i+j-1]+=kun;
	}
	tmp[0]=i+j;
	while(!tmp[tmp[0]]) tmp[0]--;
}
bool compare(int a[],int b[]){
	if(a[0]<b[0]) return true;
	if(a[0]>b[0]) return false;
	for(int i=a[0];i>0;i--){
		if(a[i]<b[i]) return true;
		return false;
	}
}
int main(){
	scanf("%d%d%s",&n,&k,s+1);
	for(int i=1;i<=n;i++){
		a[i][i][0]=1;
		a[i][i][1]=s[i]-'0';
		for(int j=i+1;j<=n;j++){
			memcpy(a[i][j],a[i][j-1],sizeof a[i][j-1]);
			a[i][j][0]++;
			a[i][j][a[i][j][0]]=s[j]-'0';
		}
	}
	for(int i=1;i<=n;i++) memcpy(dp[i][0],a[1][i],sizeof a[1][i]);
	for(int len=1;len<=k;len++){
		for(int i=len+1;i<=n;i++){
			for(int j=len;j<i;j++){
				mul(dp[j][len-1],a[j+1][i]);
				if(compare(dp[i][len],tmp)) memcpy(dp[i][len],tmp,sizeof tmp);
			}
		}
	}
	for(int i=dp[n][k][0];i>0;i--) printf("%d",dp[n][k][i]);
	return 0;
}
2024/8/24 12:55
加载中...