noi1999生日蛋糕

关键词：

题目背景

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

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

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

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

令Q= Sπ

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

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

题目描述

输入输出格式

输入格式：

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

输出格式：

仅一行，是一个正整数S（若无解则S=0）。

输入输出样例

100
2

68
分析：裸搜只有10分。。。。。。其实这就是一道搜索的题，关键是要怎么剪枝。可以很容易想出两个剪枝：
1.当前体积+以后的最小体积>n,剪枝.
2.当前表面积+以后的最小表面积>ans,剪枝.
第一个是很好处理的，关键是第二个剪枝，如果直接用最小的i和h来算，在体积上不能保证满足要求，有一个定理是如果体积一定，半径越大，表面积越小，因为在体积中半径的增长是平方级的，这样我们接下来每一层和这一层的半径相同，那么就是最小表面积了（虽然永远也达不到，但是不会把正解给剪掉），保证体积满足要求，我们只需要用剩下的体积除以当前层的半径就好了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int inf = 0x7ffffff;

int n,m,ans = inf,qs[50],qv[50];

void dfs(int cnt,int s,int v,int r,int h)
{
    if (cnt == 0)
    {
        if (v == n)
        ans = min(ans,s);
        return;
    }
    //剪枝
    if (v + qv[cnt] > n)
    return; 
    if (s + (n - v) / r > ans)
    return;
    for (int i = r - 1; i >= cnt; i--)
    {
        if (cnt == m)
        s = i * i;
        for (int j = h - 1; j >= cnt; j--)
              dfs(cnt - 1,2 * i * j + s,v + i * i * j,i,j);
    } 
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; i++)
    {
        int t2 = i * i * i;
        qv[i] += qv[i-1] + t2;
    }
    dfs(m,0,0,sqrt(n),n);
    if (ans != inf)
    printf("%d
",ans);
    else
    printf("0
");
    
    return 0;
 } 
 

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[noi1999]生日蛋糕(dfs)(代码片段)

P1731[NOI1999]生日蛋糕(dfs)已知：∑i=1mri2hi=N\\sum\\limits_i=1^mr_i^2h_i=Ni=1∑m​ri2​hi​=N求min((∑i=1m2rihi)+rm2)min((\\sum\\limits_i=1^m2r_ih_i)+r_m^2)min((i=1∑m​2ri​hi​)+rm2​)2×1043≈27\\sqrt[3]2\\times10^4\\approx... 查看详情

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

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

[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)次后，连同最后... 查看详情

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 查看详情

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

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

bzoj1867:[noi1999]钉子和小球dp(代码片段)

设f[i][j]为掉到f[i][j]时的概率然后分情况随便转移一下就好主要是要手写分数比较麻烦#include<iostream>#include<cstdio>usingnamespacestd;constintN=55;intn,m;chara[N][N];longlonggcd(longlonga,longlongb)return!b?a:gcd(b,a%b);s 查看详情

[bzoj1867][noi1999][钉子和小球](动态规划)

DescriptionInput第1行为整数n（2<=n<=50）和m（0<=m<=n）。以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。Output仅一行... 查看详情

bzoj千题计划189：bzoj1867:[noi1999]钉子和小球

http://www.lydsy.com/JudgeOnline/problem.php?id=1867 dp[i][j]落到（i，j）的方案数dp[i][j]=0.5*dp[i-1][j] [(i-1,j)位置有钉子]+0.5*dp[i-1][j-1]  [（i-1.j-1）位置有钉子]+dp[i-1][j-2]  [（i-1，j-2） 查看详情

noi1999jzyzoj1289棋盘分割dp方差的数学结论

http://172.20.6.3/Problem_Show.asp?id=1289除了下标一坨一坨屎一样挺恶心其他都还挺容易的dp，这道题才发现scanf保留小数位是四舍五入的，惊了。f[k][x1][y1][x2][y2]嗯写的时候猜错结论了，本来以为是求下属分配方案中平方和与平均数平方... 查看详情

bzoj3672[noi2014]购票树分治+斜率优化

...14]购票Description 今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国n个城市的OIer们都会从各地出发，到SZ市参加这次盛会。    全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为... 查看详情

bzoj3672:[noi2014]购票

Description今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国n个城市的OIer们都会从各地出发，到SZ市参加这次盛会。全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的n... 查看详情

bzoj3672/uoj7[noi2014]购票

...sp;Description 　　今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国n个城市的OIer们都会从各地出 查看详情

将facebook用户生日存储到mysql

】将facebook用户生日存储到mysql【英文标题】：Storingfacebookuserbirthdaytomysql【发布时间】：2013-01-0819:35:00【问题描述】：我正在使用Codeigniter和mysql。我得到了1999年1月23日格式的facebook用户生日我在mysql表中得到日期YYYY/M/D格式。如... 查看详情

p2564[scoi2009]生日礼物？

...没有彩珠，但多个彩珠也可以出现在同一个位置上。小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带 查看详情

用java的date类输入一个人的生日并输出，求代码。

      //生日字符串和整型 String birthDateString = "1999-09-09"; int year = 1999; int month = 9; int day = 9; //将字符串转换为Date DateFormat dateFormat = new ... 查看详情