#9TLE求调
查看原帖
#9TLE求调
1054383
c_legg楼主2024/8/30 19:12
#include <stdio.h>
#include <math.h>

int n, m, ans=2147483647;

int r[30], h[30];

int readint() {
	int num=0, c=0, t=1;
	while(c>'9' || c<'0') {
		c=getchar();
		if(c=='-') t=-1;
	}
	while(c<='9' && c>='0') {
		num=num*10+c-'0';
		c=getchar();
	}
	return num*t;
}

void dfs(int v, int x, int s) {
//剩余体积vπ,第x层,侧面积s
	if(v<0 || x<0 || s+r[m]*r[m]>=ans) return ;
	if(x+r[m]*r[m]+s>=ans) return ;
	if(x<m && x*r[m]*r[m]*h[m]<v) return ;
	if(v==0 && x==0) {
		ans=s+r[m]*r[m];
		return ;
	}
	for(int i=x; i<r[x+1]; i++) {
		for(int j=x; j<h[x+1]; j++) {
			if(2*i*j+x-1+r[m]*r[m]+s>=ans) continue;
			if(x*i*i*j<v) continue;
			if(v-i*i*j<0 || x-1<0 || s+2*i*j+r[m]*r[m]>=ans) continue;
			r[x]=i, h[x]=j;
			dfs(v-i*i*j, x-1, s+2*i*j);
			r[x]=0, h[x]=0;
		}
	}
}

int main() {
	n=readint(), m=readint();
	
	r[m+1]=h[m+1]=pow(n, 2.43/3.0)+1;
	dfs(n, m, 0);
	printf("%d", (ans==2147483647 ? 0 : ans));
	return 0;
}
2024/8/30 19:12
加载中...