poj1190深搜 生日蛋糕
题意:
让你制作一个蛋糕,这个蛋糕有m层,而且每层都是圆柱形,并且每一层都必须满足
ri>ri+1 && hi > hi+1,然后给出蛋糕的总体积是n*PI,还有层数m,让你构建一个蛋糕,使得这个蛋糕的总面积(没有底面)S*PI中的S最小,其中S,m,n,ri,hi都是整数(n<=10000,m<=20)。
思路:
题意的最后一句话是突破口,就是所有的数据都是整数,这样我们可以考虑搜索,就是枚举每一层的r,h,下面来说一下剪枝,这个题目剪枝是关键
(1)r可以直接从sqrt(n)跑,h得从n跑 ,这个只是大致算的
(2)枚举的时候一定要注意,r,h下限不是1,而是剩余的层数+1,因为每层都至少-1
(3)对于每一个状态,求出当前状态的最大体积,如果小于n,那么直接return
(4)对于每一个状态,求出当前状态的最小体积,如果大于n,那么直接return
至于怎么求最大最小体积,要根据ri>ri+1&&hi>hi+1,自己去吧剩下的层数的r,h都构建出来求。别的没什么,题目比较简单,但是做着挺有感觉的。
#include<stdio.h>
#include<math.h>
int ansS ,m ,n;
bool jude(int nowi ,int r ,int h ,int v)
{
int vv = v + r * r * h;
for(int i = 1 ;i <= m - nowi ;i ++)
{
vv += i * i * i;
if(vv > n) return 0;
}
for(int i = nowi ;i <= m ;i ++)
{
v += r * r * h;
r -- ,h --;
}
if(v < n) return 0;
return 1;
}
void DFS(int nowi ,int R ,int H ,int nowv ,int nows)
{
if(nowv > n || ansS && nows > ansS) return ;
if(nowi == m + 1)
{
if(nowv == n)
if(ansS == 0 || ansS > nows) ansS = nows;
return ;
}
for(int i = R ;i > m - nowi ;i --)
for(int j = H ;j > m - nowi ;j --)
{
int ts = nows + 2 * i * j + i * i;
if(nowi != 1) ts -= i * i;
if(jude(nowi ,i ,j ,nowv))
DFS(nowi + 1 ,i - 1 ,j - 1 ,nowv + i * i * j ,ts);
}
return;
}
int main ()
{
scanf("%d %d" ,&n ,&m);
ansS = 0;
DFS(1 ,int(sqrt(n*1.0)) ,n ,0 ,0);
printf("%d\n" ,ansS);
return 0;
}
最新文章
- 用TypeScript开发爬虫程序
- PHP采集程序中的常用函数
- codeforces 486B.OR in Matrix 解题报告
- centos 安装php-fpm , nginx二级域名配置 ,但为什么必须要 域名提供商 哪里解析新的二级域名一下 才能用呢?
- C(m,n)%P
- Validate Binary Search Tree 解答
- 又优化了一下 Android ListView 异步加载图片
- ubuntu下发布asp.net core并用nginx代理之旅(续)
- Fiddler的script用法
- HTML&;CSS
- python摸爬滚打之day032 管道 数据共享 进程池
- Eclipse设置所有新创建文件默认格式为UTF-8
- Linux下rsyslog日志收集服务环境部署记录
- xlrd、xlwt 操作excel表格详解
- FB01与F-02的区别(转载)
- poj2082 Terrible Sets(单调栈)
- logistic回归和softmax回归
- CF1017G The Tree 树链剖分
- Codeforces 1073G Yet Another LCP Problem $SA$+单调栈
- JavaWeb基于session和cookie的数据共享