CodeVS 1710 生日蛋糕 题解

#include <cstdio>
using namespace std;

int N, M;
int ans = ~0u>>1;
bool flag;

void DFS(int R, int H, int V, int S, int m){
	if(S>ans)return;
	if(V>R*R*H*m)return;
	if(m && !V)return;
	if(!m && V)return;
	if(R<m)return;
	if(H<m)return;
	if(V<0)return;
	if(m<0)return;
	if(V==0 && m==0){
		if(ans > S)ans = S, flag = true;
		return;
	}
	for(int r = R; r>=m; --r)for(int h = H; h>=m; --h)DFS(r-1, h-1, V-r*r*h, S+2*r*h, m-1);
}

int main() {
	scanf("%d %d", &N, &M);
	for(int R = 70; R>=M; --R)for(int H = (N/R/R); H>=M; --H)DFS(R-1, H-1, N-R*R*H, R*R+2*R*H, M-1);
	if(flag) printf("%d\n", ans);
	else printf("0\n");
	return 0;
}

 

上一篇:leetcode-算法-1710. 卡车上的最大单元数


下一篇:Truck History最小生成树