Next Spaceship

Driving into future…

POJ 1190 Birthday Cake Report

| Comments

View this problem on POJ: 1190 Birthday Cake (生日蛋糕)

There is no good methods, maybe dynamic programing is feasible, but it’s too complex for me to construct the transformation equation.

I have to use DFS (Depth First Search) to solve this problem. After the TLE (Time Limit Exceeds) appeared enough times, I worked it out. Pruning is very important for this problem.

My source code:

POJ 1190 Birthday Cake
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cmath>
using namespace std;
int n,m;
int q[11000];
int p[11000];
unsigned int result;
void dfs(int l,int v,int r,int h,int s){
    if(v<0)return;
    if(l>m+1)return;
    if(s+p[m-l+1]>result)return;
    if(v<q[m-l+1])return;
    if(v>r*r*h*(m-l+1))return;
    if(l==m+1&&v==0){
        if(s<result)result=s;
    }
    int ri,hi;
    for(ri=r;ri>0;ri--){
        if(2*v/ri>=result-s)break;
        for(hi=h;hi>0;hi--){
            int t=s+2*ri*hi;
            if(l==1)t+=ri*ri;
            dfs(l+1,v-ri*ri*hi,ri-1,hi-1,t);
        }
    }
}
int main(){
    cin>>n>>m;
    result=-1;
    int i;
    for(i=0;i<11000;i++){
        q[i]=i*i*i;
        p[i]=2*i*i;
    }
    for(i=1;i<11000;i++){
        q[i]+=q[i-1];
        p[i]+=p[i-1];
    }
    dfs(1,n,(int)(sqrt((double)n)),n,0);
    if(result==-1)cout<<"0";
    else
        cout<<result;
    return 0;
}

Comments