P1018 80分求助
查看原帖
P1018 80分求助
531776
LYM20114楼主2022/8/29 08:53
#include <iostream>
#include <cstring>
using namespace std;
int len,k;
string num;
unsigned __int128 f[45][45][8];
bool vis[45][45][8];
void print(unsigned __int128 x){
    if(x >= 10) print(x / 10);
    putchar(x % 10 + '0');
}
unsigned __int128 dp(int l,int r,int K){
	if(vis[l][r][K]) return f[l][r][K];
	if(K == 0){
		__int128 res = 0;
		for(int i = l;i <= r;i++)
			res = res * 10 + int(num[i] - '0');
		vis[l][r][K] = 1;
		f[l][r][K] = res;
		return f[l][r][K];
	}
	for(int i = l;i < r;i++)
		for(int j = 0;j < K;j++)
			f[l][r][K] = max(f[l][r][K],dp(l,i,j) * dp(i + 1,r,K - 1 - j));
	vis[l][r][K] = 1;
	return f[l][r][K];
}
int main(){
	memset(f,0,sizeof f);
	memset(vis,0,sizeof vis);
	cin >> len >> k >> num;
	print(dp(0,len - 1,k));
	return 0;
}
2022/8/29 08:53
加载中...