求助,磕了5个小时的,热乎的wa0分
查看原帖
求助,磕了5个小时的,热乎的wa0分
244597
kabout楼主2021/2/17 14:11
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=INT_MAX,ch1[22]= {0,1,9,36,100,225,441,784,1296,2025,3025,4356,6084,8281,11025,14400,18496,23409,29241,36100,44100},ch3[22]= {0,2,10,28,60,110,182,280,408,570,770,1012,1300,1638,2030,2480,2992,3570,4218,4940,5740};
//ch1是最小体积的前缀和数组,ch3是最小侧面积的前缀和数组
void dfs(int step,int left,int rl,int hl,int S) {//step第几层,left剩下体积,rl上一层的半径,hl上一层的高,S累加面积 
	if(left<ch1[step])return;//剩下的体积不足以堆上去 
	if(S+ch3[step]>=ans)return;//剩下的最小侧面积也大于答案 
	if(!step) {//结束 
		if(!left&&S<ans)ans=S;//更新答案 
		return;
	}
	int r=sqrt(left);//圆柱体积公式,一本通的 
	for(int r=min(rl-1,r); r>=step; r--) {//枚举r 
		if(r/2<=min(left/(r*r),hl-1)&&r/2>=step) {//因为这种情况下r=2h的时候侧面积加上一个顶面积才最小,特殊判断 
			if(step==m)dfs(step-1,left-r*r*r/2,r,r/2,S+r*2*r/2+r*r);//底层的时候就加上底面积 
			else dfs(step-1,left-r*r*r/2,r,r/2,S+r*2*r/2);
		}

		for(int h=min(left/(r*r),hl-1); h>=step; h--) {//枚举h 
			if(step==m)dfs(step-1,left-r*r*h,r,h,S+r*2*h+r*r);
			else dfs(step-1,left-r*r*h,r,h,S+r*2*h);
		}
	}
}
int main() {
	cin>>n>>m;
	if(ch1[m]>n) {//不能搜索的直接输出 
		cout<<0<<endl;
		return 0;
	}
	dfs(m,n,sqrt(n),sqrt(n),0);// 初始值定大一点 
	cout<<ans<<endl;
	return 0;
}
2021/2/17 14:11
加载中...