POJ 1190(深搜)
2024-08-23 22:25:43
http://poj.org/problem?id=1190
又有好久没做搜索的题了,没想到做一个卡了我那么久,想哭啊。
一个中文题,思路呢也就是搜索呗,一层一层往上面搜,不过这里有两个比较重要的地方的剪枝。
一、每一次搜索可以达到的最小的半径和高度为当前总的层数减去当前层数(我是默认为最底层是第1层的)。
二、上一层的总面积和加上这一层的最大面积和如果大于最小的表面积的话,直接返回。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h> using namespace std;
#define INF 9999999 int s=INF,m,n,ans,mv[]; int dfs(int r,int h,int x,int y)
{
for(int i=r-;i>=(n-y);i--)
for(int j=h-;j>=(n-y);j--)
{
if(x+*(m-ans)/r>=s) return ;
if(x>s) return ;
if(ans+i*i*j<m&&y!=n&&i!=&&j!=){
ans+=i*i*j;
if(y==) x+=i*i; //如果有多层的话,那么表面的总面积和就等于最底下的蛋糕的表面积。(从上往下看)
dfs(i,j,x+*i*j,y+);
if(y==) x-=i*i;
ans-=i*i*j;
}
if(ans+i*i*j==m&&y==n){
x+=*i*j;
if(y==) x+=i*i; //如果只有一层的话,那么上表面积也就等于半径的平方。
if(x<s) s=x;
x-=*i*j;
if(y==) x-=i*i; //这里记得要减。
}
}
return ;
} int main()
{
scanf("%d%d",&m,&n);
ans=;
s=INF;
dfs(sqrt(double(m))+,m+,,);
if(s!=INF) printf("%d\n",s);
else printf("0\n");
}
最新文章
- The Road To Hadoop(网盘系统的实现)
- Yii2使用教程
- winform自定义日期控件,要求可以手动输入日期DatePicker
- MySQL用户名和密码问题
- 知道创宇研发技能表v3.0
- DRP PK 牛腩新闻发布系统
- 测缘分程序c代码简单实现
- php 技巧、高效率写法 推荐(转载+总结)
- 使用XML向SQL Server 2005批量写入数据&mdash;&mdash;一次有关XML时间格式的折腾经历
- 分享基于分布式Http长连接框架--设计模型
- Oracle问题之字符集问题,登陆sqlplus出现问号
- WPF自学入门(十)WPF MVVM简单介绍
- HTML5 唤起 APP
- SpringBoot JMS(ActiveMQ) 使用实践
- JS获取链接中域名等信息
- HDU 4553 约会安排 (区间合并)【线段树】
- MySQL firstmatch strategy
- <;构建之法>;10,11,12章的读后感
- 微软BI 之SSIS 系列 - 变量查询语句引起列输出顺序不一致的解决方法
- 如何将exe注册为windows服务,直接从后台运行