【题解】 [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;
}
上一篇:Logback简介及配置文件logback.xml详解


下一篇:输入6个成绩,冒泡排序,求平均分,再找出大于平均分的分数,最后将成绩中的偶数显示出来