sdutoj 1027 生日蛋糕 和 poj 1190

题目地址 sdutoj 1027 生日蛋糕

poj 1190 生日蛋糕

#include <stdio.h>#include <string.h>#include <math.h>#define MIN 999999999   //最优解的初始值，如果初始值不变，无解int N;  //总体积int M;  //蛋糕的层数int S = MIN;  //最优解，即最小表面积int oneToI_1S;  //[1, i-1]层侧面积之和int oneToI_1V;  //[1, i-1]层体积之和void DFS(int i, int oneToI_1S, int oneToI_1V, int R, int H);int nSanCiMiQiuHe(int x);  //计算1-x的三次幂的和。此题分析知，体积的理论最小值，R=H=当前层int MianJi(int x);  //计算面积的理论最小值，R=H=当前层int main(){    scanf("%d%d", &N, &M);    DFS(1, 0, 0, sqrt(N)+1, N+1);    if (S == MIN)    {        printf("0\n");    }    else    {        printf("%d\n", S);    }    return 0;}void DFS(int i, int oneToI_1S, int oneToI_1V, int R, int H){    if (i == M+1)  //搜完M层后结束    {        if ((oneToI_1V == N) && (oneToI_1S < S))        {            S = oneToI_1S;  //给最优解赋值        }        return ;    }    //没有剪枝AC就是做梦,难点    //1、还没到M层，当前表面积+还没搜的层数的理论最小值之和>=最优值，    //   此时没有必要再往下搜了，剪枝    //2、还没到M层，当前体积+还没搜的层数的理论最小值之和>=总体积，    //     此时没有必要再往下搜了，剪枝    //3、最重要的剪枝。因为提交了好几次，超时，那么说还应该剪枝。    //   我就要想方设法找到的数学关系式。变量有oneToI_1S 和 oneToI_1V, R, H.    //   找关系吧，R,H不应该有关系，直觉，应该在体积和表面上下功夫    //①式 N-oneToI_1V = 从第i层到M层体积求和得Ri*Ri*Hi + ... + RM*RM*HM    //②式 把①式的值放大一下，    //     即把第二个 Ri..M 都改成Ri-1    //     即Ri*Ri-1*Hi + ... + RM*Ri-1*HM.  为了凑出oneToI_1S，    //     因为oneToI_1S = S - 2*②/Ri-1    //     又因为①<②    //     所以(N-oneToI_1V) < (S-oneToI_1S)*(Ri-1)/2    //     整理得 2*(N-oneToI_1V)/Ri-1 + oneToI_1S < S,    //     到此找到了剪枝的数学表达式2*(N-oneToI_1V)/Ri-1 + oneToI_1S >= S    if ((oneToI_1S+MianJi(M-i+1) > S) || (oneToI_1V+nSanCiMiQiuHe(M-i+1) > N)        || (2*(N-oneToI_1V)/R + oneToI_1S >= S))    {        return ;    }    int radius; //第i层的半径    int high;   //第i层得高    int theoreticalMaximum;  //理论上的最大高度，从这个高度逐个减一，搜索合适的高    for (int radius=R-1; radius>=M-i+1; radius--)    {        if (i == 1)  //最底下的那一层蛋糕，那么就求出上表面的面积        {            oneToI_1S = radius * radius;        }        if ((H-1) <= ((N-oneToI_1V-nSanCiMiQiuHe(M-i))/(radius*radius)))        {            theoreticalMaximum = H-1;        }        else        {            theoreticalMaximum = (N-oneToI_1V-nSanCiMiQiuHe(M-i))/(radius*radius);        }        for (int high=theoreticalMaximum; high>=M-i+1; high--)        {            DFS(i+1, oneToI_1S+2*radius*high, oneToI_1V+radius*radius*high, radius, high);        }    }}int nSanCiMiQiuHe(int x)  //网上搜了一下求和公式为1^3+2^3+3^3+……+n^3=[n(n+1)/2]^2{    return x*(x+1)*x*(x+1)/4;}int MianJi(int x)  //网上一下搜12+22+32+....+n2=n(n+1)(2n+1)/6{    return 2*x*(x+1)*(2*x+1)/6;  //求面积2*R*H,所以前面有一个2}