首页 > 代码库 > poj1190生日蛋糕--DFS

poj1190生日蛋糕--DFS

2024-09-09 18:55:03   215人阅读

题目数据范围10000，因此简单的DFS会超时，所以要格外注意剪枝。

1.半径r，与高h都从n+1，开始搜索。

2.当前的表面积，加上之后层的预估最小表面积，若大于最优解，减掉。

3.当前的体积，加上之后层的预估最小体积，若大于最优解，减掉。

4.DFS中，若体积超出限制n，则减掉。

5.(目前体积-已有体积)/r*2+已有的表面积若大于已经得到过的S则减掉。

#include<stdio.h>
int r[10001];
int h[10001];
int N,M,S;
int miv[21];
int mis[21];
void dfs(int smm,int v,int dep,int h,int r){
    if(v>N) return;
    if(dep==0){
        if(v==N&&smm<S){
            S=smm;
            return;
        }
    }
    if(v+miv[dep-1]>N||smm+mis[dep-1]>=S||(N-v)/r*2+smm>S) return;
    for(int i=r-1;i>=dep;i--){
        if(dep==M) smm=i*i;

        int mxh;
        if((N-v-miv[dep-1])/(i*i)>h-1)
            mxh=h-1;
        else mxh=(N-v-miv[dep-1])/(i*i);
        for(int j=mxh;j>=dep;j--){
            dfs(smm+2*i*j,v+i*i*j,dep-1,j,i);
        }
    }
}
void mx(){
    for(int i=1;i<=20;i++){
        miv[i]=miv[i-1]+i*i*i;
        mis[i]=mis[i-1]+2*i*i;
    }
}
int main(){
    scanf("%d %d",&N,&M);
    S=99999999;
　　 mx();
    dfs(0,0,M,N+1,N+1);
    if(S==99999999) S=0;
    printf("%d\n",S);
    return 0;
}

 

poj1190生日蛋糕--DFS


联系
我们