正文

p1731[noi1999]生日蛋糕(dfs)(代码片段)

Harris-H  Harris-H  2023-02-04  198

关键词：

P1731 [NOI1999] 生日蛋糕(dfs)

已知： $\\sum\\limits_i=1^m r_i^2h_i=N$

求 $min((\\sum\\limits_i=1^m 2r_ih_i)+r_m^2)$

$\\sqrt[3]2\\times 10^4\\approx 27$

所以考虑搜索+剪枝。

具体看代码就好啦

#include<bits/stdc++.h>
using namespace std;
//体积公式:v=piRH
//侧面积:2piRH
//底面积:piR^2
const int MAXN=0x3f3f3f;
const int N=20007;
int ans=MAXN;
int mins[N],minv[N],n,m;
void dfs(int now,int r,int h,int s,int v) 
	//  当前层数 半径  高度 面积  体积
	int MAXN_high=h;
	if(now==0) 
		if(v==n) 
			ans=min(ans,s);
		
		return ;
	
	if(s+mins[now-1]>=ans) return ;//如果面积已经大于了目前的最优值ans就可以退出了
	if(v+minv[now-1]>n) return;//如果当前搜到的体积已经大于了题目给定的体积就可以退出了
	if(2*(n-v)/r+s>=ans)  return; //由体积推出的表面积已经大于最大值了就可以退出了
	for(int i=r-1; i>=now; --i) //枚举半径
		if(now==m) s=i*i;//此处是处理最下面的那个面其实也就是上面的那个，可以看一下解释
		MAXN_high=min(h-1 ,(n-minv[now-1]-v)/i/i);//求出最大的高度来
		for(int j=MAXN_high; j>=now; --j) 
			dfs(now-1,i,j,s+2*i*j,v+i*i*j);
		
	

int main() 
	cin>>n>>m;
	/*初始化每层成最小的表面积和体积*/
	for(int i=1; i<=m; ++i) 
		mins[i]=mins[i-1]+2*i*i;//计算面积
		minv[i]=minv[i]+i*i*i;//计算体积
	
	dfs(m,n,n,0,0);//开始dfs喽
	if(ans==MAXN) cout<<0<<'\\n';
	else cout<<ans<<'\\n';
	return 0;

noi1999生日蛋糕

...17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约... 查看详情

noi1999生日蛋糕

...7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节... 查看详情

nc16857[noi1999]生日蛋糕

...7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1≤i≤M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约... 查看详情

洛谷p1731生日蛋糕

P1731生日蛋糕题目背景7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕... 查看详情

洛谷p1731生日蛋糕

[noi1999]生日蛋糕(代码片段)

看题洛谷传送门(食用更佳)点击查看复杂的题目题目背景数据加强版link示例图：样例#1样例输入#11002样例输出#168ok,开始愉快的AC之旅第一步：预处理定义a,b数组，存储第i层最多能用的表面积和体积，便于优化第二步：深度优先搜... 查看详情

poj1190生日蛋糕--dfs

题目数据范围10000，因此简单的DFS会超时，所以要格外注意剪枝。1.半径r，与高h都从n+1，开始搜索。2.当前的表面积，加上之后层的预估最小表面积，若大于最优解，减掉。3.当前的体积，加上之后层的预估最小体积，若大于最... 查看详情

poj1190生日蛋糕dfs

生日蛋糕TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 18225 Accepted: 6486Description7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M) 查看详情

[noi1999]棋盘分割（推式子+dp）

http://poj.org/problem?id=1191棋盘分割TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 15655 Accepted: 5556Description将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续... 查看详情

poj1991noi1999棋盘分割

棋盘分割TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:15581 Accepted:5534Description将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后... 查看详情

poj1190生日蛋糕[dfs剪枝]

生日蛋糕TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 18236 Accepted: 6497Description7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i< 查看详情

noi4_1_1999[日志排序]

复杂的判断&多余的空格=n个wronganswertypeevent=recordst:string[100];year,mon,day,hour,min,sec,lse:integer;t:longint;end;vara:array[1..10000]ofevent;n:longint;functionbigger(i,j:integer):boolean;beginifa[i].ye 查看详情

生日蛋糕—dfs

...7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为... 查看详情

生日蛋糕（dfs）（搜索剪枝）生日蛋糕

1277:生日蛋糕时间限制:1Sec 内存限制:128MB提交:28 解决:10[提交][状态][讨论版]题目描述7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为nπ的m层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1≤i≤m)层蛋糕是... 查看详情

bzoj1867:[noi1999]钉子和小球（dp）

　　一眼题...输出分数格式才是这题的难点QAQ　　学习了分数结构体...#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>#definelllonglongusingnamespacestd;constintmax 查看详情

生日蛋糕(poj1190)(dfs剪枝)(代码片段)

bzoj1024[scoi2009]生日快乐-dfs

1024:[SCOI2009]生日快乐TimeLimit: 1Sec MemoryLimit: 162MBDescription　　windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为X和Y的矩形蛋糕。现在包括windy，一共有N个人来分这块大蛋糕，要求每个人必须获... 查看详情

[noi2013]树的计数

题目描述能评测了哦。我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的DFS序以及BFS序。两棵不同的树的DFS序有可能相同，并且它们的BFS序也有可能相同，例如下面两棵树的DFS序都是12453... 查看详情