能用的剪枝都用了……还是过不去
查看原帖
能用的剪枝都用了……还是过不去
184271
l55584楼主2022/8/27 11:13
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define rep(a,b,c) for(register int a=b;a<=c;++a)
#define rrep(a,b,c) for(register int a=b;a>=c;--a)
#define pi acos(-1)
using namespace std;
const int N=1e5+5,inf=0x3f3f3f3f;
int n,m;
int ss[21],sv[21];
int mmin;
void dfs(int rn,int s,int t,int las_r,int las_h)
{
	if(!t)
	{
	//	cout<<" :"<<rn<<endl;
		if(rn==0)
			mmin=min(mmin,s);
		return;
	}
//	cout<<rn<<" "<<s<<" "<<t<<" "<<las_r<<" "<<las_h<<" "<<mmin<<" "<<ss[t]<<endl;
	if(s+(2*rn)/las_r>=mmin) return;
	
	if(rn<sv[t]) return ;
	int R=min(las_r-1,(int)sqrt((rn-sv[t-1])/t));
	for(int r=R;r>=t;--r)
	{
		int H=min(las_h-1,(rn-sv[t-1])/(r*r));
		for(int h=H;h>=t;--h)
		{
			if(rn>=r*r*h)
			{
				dfs(rn-r*r*h,s+2*r*h,t-1,r,h);
			}
			
		}
	}
}
int main()
{
//	freopen("in.in","r",stdin);
	cin>>n>>m;
	mmin=inf;
	rep(i,1,m)
	{
		ss[i]=ss[i-1]+2*i*i;
		sv[i]=sv[i-1]+i*i*i;
		//cout<<ss[i]<<" "<<sv[i]<<endl;
	}
	for(int r=m;r*r*m<=n-sv[m-1];++r)
	{
		for(int h=m;h*r*r<=n-sv[m-1];++h)
		{
			//cout<<r<<" "<<h<<endl;
			dfs(n-r*r*h,r*r+2*r*h,m-1,r,h);
		}
	}
	if(mmin==inf) cout<<"0";
	else
	cout<<mmin;
	return 0;
}

麻烦大佬了

2022/8/27 11:13
加载中...