这题我有剪枝了,为啥还是20分呢,有木有大佬帮我康康,谢啦
查看原帖
这题我有剪枝了,为啥还是20分呢,有木有大佬帮我康康,谢啦
284521
queen_street楼主2022/3/18 00:13
#include<bitsdc++.h>
using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

int n,m,a[21],b[21],minn=1e8,mr=-1e8;

void dfs(int x,int v,int q,int pr,int ph) //x:层数 v:当前体积 q:当前表面积 
{
	int i,j;
	if(x==0 && v==n)
	{
//		a[m]=max(a[m],v);
		minn=min(q,minn);
//		mr=max(mr,pr);
		return;
	}
	else if(v==n || x==0)
	{
		return;
	}
	if(v+b[x-1]>n) 
		return; 
	if(q+a[x-1]>=minn)
		return;
/*	else if(x<0 || v>n || (v+b[x-1])>n)
	{
		return;
	}
	if(a[x]!=1e8)
	{
		dfs(1,)
	}*/
	for(i=pr-1;i>=x;i--)
	{
		int s=0;
		if(x==m)
		{
			s=i*i;
		}
		for(j=ph-1;j>=x;j--)
		{
			/*if(v+i*i*j>n)
			{
				break;
			}*/
//			else
			{
				dfs(x-1,v+i*i*j,s+q+2*i*j,i,j);
			}
		}
	}
}

int main()
{
	int i,j;
	n=read();
	m=read();
	//a[1]=1*1+2*1*1;
	//b[1]=1*1*1;
	for(i=1;i<=m;i++)
	{
		a[i]=a[i-1]+2*i*i;
		b[i]=b[i-1]+i*i*i;
	}
	/*for(i=1;;i++)
	{
		if(i*i>n)
			break;
		for(j=1;;j++)
		{
			if(i*i*j>n)
			{
				break;
			}
			else
				dfs(2,i*i*j,2*i*j+i*i,i,j);
		}
	}*/
	dfs(m,0,0,n,n);
	if(minn==1e8)
	{
		printf("%d",0);
		return 0;
	}
	printf("%d",minn);
	return 0;
}

2022/3/18 00:13
加载中...