90 求助!
查看原帖
90 求助!
162133
_gcl楼主2021/10/7 21:25

调了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;
}
2021/10/7 21:25
加载中...