洛谷P1731 [NOI1999]生日蛋糕(爆搜)

题目背景

7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层

生日蛋糕,每层都是一个圆柱体。

设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时,要求 R_i>R_{i+1}Ri​>Ri+1​ 且 H_i>H_{i+1}Hi​>Hi+1​ 。

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

令Q= Sπ

请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。

(除Q外,以上所有数据皆为正整数)

题目描述

输入输出格式

输入格式:

有两行,第一行为N(N<=20000),表示待制作的蛋糕的体积为Nπ;第二行为M(M<=15),表示蛋糕的层数为M。

输出格式:

仅一行,是一个正整数S(若无解则S=0)。

输入输出样例

输入样例#1: 复制

100
2

输出样例#1: 复制

68

emmmm不会做。。。

直到看了标签是“搜索”。。。

那就开心的搜吧。。

可以推出式子

$$N = \sum_{i = 1}^M R_i * R_i * H_i$$

$$S = R_1^2 + 2 * \sum_{i  = 1}^M R_i H_i$$

时间复杂度:$O(玄学)$

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
#define LL long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
int H[16], R[16];
int ans = INF;
void dfs(int now, int sum, int nowans) {
    if(sum > N || (nowans + R[1] * R[1]) > ans) return ;
    if(now == M + 1) {
        if(sum == N) 
            ans = min(ans, nowans + R[1] * R[1]); 
        return ;
    }
    if(sum + R[now - 1] * R[now - 1] * H[now - 1] * (M - now + 1) < N) return ;
    //如果后面都用最大的体积仍然不能达到要求
    if(nowans + (M - now + 1) + R[1] * R[1] > ans) return ; 
    //加上最小的仍然大于答案 
    for(int i = M - now + 1; i < H[now - 1]; i++) {
        for(int j = M - now + 1; j < R[now - 1]; j++) {
            H[now] = i; R[now] = j;
            dfs(now + 1, sum + R[now] * R[now] * H[now], nowans + 2 * R[now] * H[now]);
            H[now] = 0; R[now] = 0;
        }
    }
}
main() {
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif 
    
    N = read(); M = read();
    H[0] = sqrt(N); R[0] = sqrt(N);
    dfs(1, 0, 0);
    printf("%d", ans == INF ? 0 : ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

01:谁考了第k名 个人博客:doubleq.win

个人博客:doubleq.win 01:谁考了第k名 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 在一次考试中,每个学...

37350
来自专栏Crossin的编程教室

【每周一坑】谁是哪国人?

一道比较老套的题目: 在一个宾馆里住着六个不同国籍的人,他们分别来自美国、德国、英国、法国、俄罗斯和意大利。他们的名字叫 A、B、C、D、E、F。名字的顺序与...

27540
来自专栏向治洪

java解决hash算法冲突

看了ConcurrentHashMap的实现, 使用的是拉链法. 虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度...

26590
来自专栏CreateAMind

CS231n课程笔记翻译:Python Numpy教程

译者注:本文智能单元首发,翻译自斯坦福CS231n课程笔记Python Numpy Tutorial,由课程教师Andrej Karpathy授权进行翻译。本篇...

12730
来自专栏mathor

LeetCode69. x 的平方根

 这道题直接一个return Math.sqrt就出来了,但是秉承着学习的心态,尝试着用二分法ac  首先要确定的就是左右区间,左区间是0无疑了,那么右...

22020
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(二)No.50

上一次我们说完了用 HashSet 来进行计数了。我们可以发现,如果我们估计有N个数,那么我们至少需要N*32bit(按照int在32位操作系统下占用32个bi...

21180
来自专栏海天一树

NOIP 2011初赛普及组C/C++答案详解

3 C 8G = 8 * 1024 M 8 * 1024 / 2 = 4096张 注意,题目说的是“大约”,不要求精确。

17620
来自专栏小红豆的数据分析

小蛇学python(17)时间序列的数据处理

不管是在金融学、经济学的社会学科领域,还是生态学、系统神经的自然学科领域,时间序列数据都是一种重要的结构化数据形式。

21850
来自专栏owent

POJ PKU Let's Go to the Movies 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3513

8720
来自专栏数据分析

[数据分析工具] Pandas 功能介绍(二)

条件过滤 我们需要看第一季度的数据是怎样的,就需要使用条件过滤 ? 体感的舒适适湿度是40-70,我们试着过滤出体感舒适湿度的数据 ? 最后整合上面两种条件,在...

37760

扫码关注云+社区

领取腾讯云代金券