生日蛋糕 POJ - 1190 搜索 数学

http://poj.org/problem?id=1190

题解：四个剪枝。

#define _CRT_SECURE_NO_WARNINGS

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<cmath>

#include<cstdio>

#include<string>

#include<stack>

#include<ctime>

#include<list>

#include<set>

#include<map>

#include<queue>

#include<vector>

#include<sstream>

#include<iostream>

#include<functional>

#include<algorithm>

#include<memory.h>

//#define INF 0x3f3f3f3f

#define eps 1e-6

#define pi acos(-1.0)

#define e exp(1.0)

#define rep(i,t,n)  for(int i =(t);i<=(n);++i)

#define per(i,n,t)  for(int i =(n);i>=(t);--i)

#define mp make_pair

#define pb push_back

#define mmm(a,b) memset(a,b,sizeof(a))

//std::ios::sync_with_stdio(false);

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

void smain();

#define ONLINE_JUDGE

int main() {

//    ios::sync_with_stdio(false);

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

    long _begin_time = clock();

#endif

    smain();

#ifndef ONLINE_JUDGE

    long _end_time = clock();

    printf("time = %ld ms.", _end_time - _begin_time);

#endif

    return ;

}

int n, m;

int mn =  << ;

int area = ;

int mnV[];

int mnA[];

int maxVforNRH(int n, int r, int h) {

    int v = ;

    rep(i, , n - )

        v += (r - i)*(r - i)*(h - i);

        return v;

}

void  dfs(int v,int n,int r,int h) {//n层凑v，底层不超r，h

    if (n == ) {

        if (v)return;

        else {

            mn = min(mn, area);

            return;

        }

    }

    if (v <= )return;

    if (mnV[n] > v)return;//

    if (area + mnA[n] >= mn)return;//

    if (h < n || r < n)return; //

    if (maxVforNRH(n,r,h)< v)return;//

    per(rr, r, n) {

        if (n == m)area = rr*rr;

        per(hh, h, n) {

            area +=  * rr*hh;

            dfs(v - rr*rr*hh, n - , rr - , hh - );

            area -=  * rr*hh;

        }

    }

}

void Run() {

}

void smain() {

    cin >> n >> m;

    mnV[] = ;

    mnA[] = ;

    rep(i, , m) {

        mnV[i] = mnV[i - ] + i*i*i;

        mnA[i] = mnA[i - ] +  * i*i;

    }

    if (mnV[m] > n)cout <<  << endl;

    else {

        int maxH = (n - mnV[m - ]) / (m*m) + ;

        int maxR = sqrt(double(n - mnV[m - ]) / m) + ;//底层最大的H，R

        area = ;

        mn =  << ;

        dfs(n, m, maxH, maxR);

        if (mn ==  << ) {

            cout <<  << endl;

        }

        else cout << mn << endl;

    }

    Run();

}