调了114514遍了还是没过。。第二个点WA(返回无穷大,没有更新到)。
发现把41行删去后结果正确,但窝实在不知道41行哪里错了。。。求助真神们orz
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int sum=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
sum=(sum<<1)+(sum<<3)+(c^48);
c=getchar();
}
return sum*f;
}
struct node
{
int r;
int h;
} path[27];
int n,m,ans=114514000;
void dfs(int k,int now,int now1,int start1,int start2)
{
if(k==n&&now==m)
{
ans=min(ans,now1+path[0].r*path[0].r);
return;
}
if(now>=m) return;
if(k>=n)return ;
if(now1+path[0].r*path[0].r+(n-k)>=ans)return;
if(now+start1*start1*start2*(n-k)<m)return;
for(int i=start1-1;i>=n-k;i--)
{
for(int j=start2-1;j>=n-k;j--)
{
if(i*i*j>m-now)continue;//减枝2 可行性
path[k].r=i,path[k].h=j;
dfs(k+1,now+i*i*j,now1+(2*i*j),i,j);
path[k].r=0,path[k].h=0;
}
}
}
int main()
{
m=read(),n=read();
dfs(0,0,0,ceil(sqrt(m)),m);
cout<<ans;
return 0;
}