题目名称	67. [NOI 1999]生日蛋糕
输入输出	`cake.in/out`
难度等级	★★★
时间限制	2000 ms (2 s)
内存限制	128 MiB
测试数据	10
题目来源	sywgz 于2008-07-18加入
开放分组	全部用户
提交状态
分类标签	搜索法 NOI 数学剪枝
	分享题解

通过：168，提交：506，通过率：33.2%
ShallowDream雨梨	100	0.000 s	0.00 MiB	C++
Andy23	100	0.000 s	0.00 MiB	C++
Brian	100	0.000 s	0.00 MiB	C++
hyy	100	0.000 s	0.00 MiB	C++
hxc	100	0.000 s	0.00 MiB	C++
mxr2022	100	0.000 s	0.00 MiB	C++
Emine	100	0.005 s	0.06 MiB	C++
Hzfengsy	100	0.006 s	0.29 MiB	C++
睚眦一嘂	100	0.006 s	0.29 MiB	C++
evershine	100	0.006 s	0.29 MiB	C++

本题关联比赛
暑假培训三

关于生日蛋糕的近10条评论(全部评论)
#include<iostream> #include<cstdio> using namespace std; const int inf=0x3f3f3f3f; int n,m,s,minv[25],mins[25],ans=inf; void dfs(int sumv,int sums,int cur,int r,int h){ int i,j,temp; if(cur==0){ if(sumv==n)ans=min(sums,ans); return; } if(sumv+minv[cur]>n)return; if(sums+mins[cur]>ans)return; if(2(n-sumv)/r+sums>=ans)return; for(i=r-1;i>=cur;i--){ if(cur==m)sums=ii; temp=min((n-minv[cur-1]-sumv)/i/i,h-1); for(j=temp;j>=cur;j--) dfs(sumv+iij,sums+2ij,cur-1,i,j); } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ minv[i]=minv[i-1]+iii; mins[i]=mins[i-1]+2ii; } dfs(0,0,m,n+1,n+1); printf("%d",ans==inf?0:ans); } DragonLi 2017-05-14 07:16 13楼
DFS+剪枝~有一个点死都过不去QUQ CodeLyoko 2016-11-16 15:05 12楼
不行了……一遍80分之后就无计可施了，我只能伸出我罪恶的爪子了(╯▽╰) 浮生随想 2016-10-18 21:37 11楼
poj都过了，为什么cogs超时呢？？ forever 2015-08-10 17:06 10楼
stdafx.h 2015-08-10 15:50 9楼
到底要剪枝多少次！！！！！！？？？？？？石家庄二中教练 2015-03-25 21:11 8楼
搜索好题。 TA 2015-01-10 14:18 7楼
剪枝一入深似海…… cstdio 2013-05-13 21:47 6楼
打了2组表。。。明天一定再看看 QhelDIV 2012-12-17 22:32 5楼
太变态了苏轼 2008-10-15 19:05 4楼

67. [NOI 1999]生日蛋糕

★★★ 输入文件：cake.in 输出文件：cake.out 简单对比
时间限制：2 s 内存限制：128 MiB

【题目描述】

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 $i$（$1 \leq i \leq M$）层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。当 $i \leq M$ 时，要求 $R_i > R_{i+1}$ 且 $H_i > H_{i+1}$。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。

请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S=\frac{Q}{\pi}$ 最小。

（除 $Q$ 外，以上所有数据皆为正整数）

【输入格式】

第一行为一个整数 $N$（$N \leq 2 \times 10^4$），表示待制作的蛋糕的体积为 $N\pi$。

第二行为 $M$（$M \leq 25$），表示蛋糕的层数为 $M$。

【输出格式】

输出一个整数 $S$，若无解，输出 $0$。

【输入样例】

100
2

【输出样例】