社区讨论
求指教!!!!!!!!!!!!
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 条回复,欢迎继续交流。
正在加载回复...