RT爆零
查看原帖
RT爆零
757040
MuLinnnnn楼主2023/6/22 21:11
#include <bits/stdc++.h>
using namespace std;
int n, k;
char S[110];

struct BigInt{
	int len, x[110];
	BigInt(){
		len = 1;
	}
	void Print(){
		for(int i = len; i; i--){
			printf("%d",x[i]);
		}
		puts("");
	}
}dp[110][110],s[110][110];

BigInt fix(BigInt a){
	for(int i = 1; i < a.len; ++i){
		a.x[i + 1] += a.x[i] / 10;
		a.x[i] %= 10;
	}
	while(a.x[a.len] >= 10){
		a.x[a.len + 1] += a.x[a.len] / 10;
		a.x[a.len] %= 10;
		a.len++;
	}
	while(!a.x[a.len] && a.len > 1){
		a.len--;
	}
	return a;
}

inline BigInt operator *(BigInt a, int b){
	for(int i = 1; i <= a.len; ++i){
		a.x[i] *= b;
	}
	return fix(a);
}

inline BigInt operator *(BigInt a, BigInt b){
	BigInt c;
	for(int i = 0; i < 110; ++i){
		c.x[i] = 0;
	}
	c.len = a.len + b.len - 1;
	for(int i = 1; i <= a.len; ++i){
		for(int j = 1; j <= b.len; ++j){
			c.x[i + j - 1] += a.x[i] * b.x[j];
		}
	}
	return fix(c);
}

inline BigInt operator +(BigInt a, int b){
	a.x[1] += b;
	return fix(a);
}

inline bool operator <(BigInt a, BigInt b){
	if(a.len != b.len){
		return a.len < b.len;
	}
	for(int i = a.len; i; i--){
		if(a.x[i] != b.x[i]){
			return a.x[i] < b.x[i];
		}
	}
	return false;
}

int main(){
//	ios::sync_with_stdio(false);
//    cin.tie(0);cout.tie(0);
	
    scanf("%d%d",&n,&k);
    scanf("%s",S + 1);
    for(int i = 1; i <= n; ++i){
    	for(int j = 1; j <= n; ++j){
    		s[i][j] = s[i][j - 1] * 10 + (S[j] - '0');
		}
	}
	for(int i = 1; i <= n; ++i){
		dp[i][0] = s[1][i];
		for(int j = 1; j <= k; ++j){
			for(int d = j; d < i; ++d){
				dp[i][j] = max(dp[i][j], dp[d][j - 1] * s[d + 1][i]);
			}
		}
	}
	dp[n][k].Print();
	return 0;
}

照着一本通打的,爆零力(RT

2023/6/22 21:11
加载中...