【题解】 [NOI1999]生日蛋糕

题面

Solution

搜索每一层的半径和高度，然后加入一些剪枝就好了。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<iostream>

#include<map>

#define ll long long

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline int gi(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int Inf=2e9+10;

int n,m,ans=Inf,a[210],b[210];

void dfs(int v,int s,int p,int r,int h){

	if(p==0){

		if(v==n)ans=min(ans,s);

		return;

	}

	if(v+b[p-1]>n)return;

	if(s+a[p-1]>ans)return;

	if(2*(n-v)/r+s>=ans)return;

	for(int i=r-1;i>=p;--i){

		if(p==m)s=i*i;

		int Maxh=min(h-1,(n-v-b[p-1])/(i*i));

		for(int j=Maxh;j>=p;--j)

			dfs(v+i*i*j,s+2*i*j,p-1,i,j);

	}

}

int main(){

	int i,j,k;

	n=gi();m=gi();

	a[0]=0;b[0]=0;

	for(i=1;i<=28;i++){

		a[i]=a[i-1]+2*i*i;

		b[i]=b[i-1]+i*i*i;

	}

	dfs(0,0,m,n+1,n+1);

	printf("%d\n",ans==Inf?0:ans);

	return 0;

}

巴特西

【题解】 [NOI1999]生日蛋糕

题面

Solution

最新文章

热门文章