社区讨论

求指教!!!!!!!!!!!!

P1731[NOI1999] 生日蛋糕参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi6vmblg
此快照首次捕获于
2025/11/20 11:33
4 个月前
此快照最后确认于
2025/11/20 11:33
4 个月前
查看原帖
怎么优化!!!
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=999999;
int solve[25];
int max_s(int left,int f,int bl)
{
	for(int i=1;i<f;++i)
	 left-=solve[i];
	 if(left<solve[f]||bl-1<f) return 10010;
	 else return min(bl-1,(int)sqrt(left/f)); 
}
int max_h(int left,int f,int bl,int s)
{
	for(int i=1;i<f;++i)left-=solve[i];
	if(left<s*f||bl-1<f) return 10010;
	return min((int)(left/(s*s)),bl-1);
}
void dfs(int floor,int left,int ans_s,int s,int h)
{
	left-=s*s*h;
	ans_s+=2*s*h;
	if(floor==1)
	{
		if(left==0)
		{
		 ans=min(ans,ans_s);
	    }
		 return;
	}
	else
	{
		if(max_s(left,floor-1,s)==10010) return;
		else
		{
			for(int i=floor-1;i<=max_s(left,floor-1,s);++i)
			{
				if(max_h(left,floor-1,h,i)==10010) return;
				for(int j=floor-1;j<=max_h(left,1,h,i);++j)
				 dfs(floor-1,left,ans_s,i,j);
			}
		}
	}	
}
inline void init()
{
	for(int i=1;i<=21;++i) solve[i]=i*i*i;
	scanf("%d%d",&n,&m);
	for(int i=m;i<=max_s(n,m,999999);++i)
	 {
	 	for(int j=m;j<=max_h(n,m,999999,i);++j)
	 	{
	 		dfs(m,n,i*i,i,j);
	 	}
	 }
} 
int main()
{
	init();
	printf("%d",ans);
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...