洛谷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 + , INF = 1e9 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M;

int H[], R[];

int ans = INF;

void dfs(int now, int sum, int nowans) {

    if(sum > N || (nowans + R[] * R[]) > ans) return ;

    if(now == M + ) {

        if(sum == N)

            ans = min(ans, nowans + R[] * R[]);

        return ;

    }

    if(sum + R[now - ] * R[now - ] * H[now - ] * (M - now + ) < N) return ;

    //如果后面都用最大的体积仍然不能达到要求

    if(nowans + (M - now + ) + R[] * R[] > ans) return ;

    //加上最小的仍然大于答案

    for(int i = M - now + ; i < H[now - ]; i++) {

        for(int j = M - now + ; j < R[now - ]; j++) {

            H[now] = i; R[now] = j;

            dfs(now + , sum + R[now] * R[now] * H[now], nowans +  * R[now] * H[now]);

            H[now] = ; R[now] = ;

        }

    }

}

main() {

#ifdef WIN32

    //freopen("a.in", "r", stdin);

#endif

    N = read(); M = read();

    H[] = sqrt(N); R[] = sqrt(N);

    dfs(, , );

    printf("%d", ans == INF ?  : ans);

    return ;

}