萌新50分求助
查看原帖
萌新50分求助
590283
lunatics楼主2023/3/20 16:48

求大佬帮忙看看有什么地方没有考虑到,或者有什么条件写错了?

#include<bits/stdc++.h>
using namespace std;

typedef struct vol{
    int h,r;
}vol;

int n,m,ans = INT32_MAX;
stack<vol> st;

//surf:现有表面积
//volume:剩余体积
//layer:剩余层数

void dfs(int surf, int volume, int layer){
    //得到结果
    if(layer == 0 and volume == 0){
        ans = min(ans,surf);
        return;
    }
    //当前面积总和超过已有结果
    if(surf >= ans){
        return;
    }
    //当前体积超过要求
    if(volume <= 0){
        return;
    }
    //剩余最大体积加现有体积小于要求体积
    int maxvol = n - volume;
    int maxh = st.top().h - 1;
    int maxr = st.top().r - 1;
    int maxh_t = maxh;
    int maxr_t = maxr;
    for(int i = layer;i > 0;i--){
        maxvol += maxh_t*maxr_t*maxr_t;
        maxh_t--;
        maxr_t--;
    }
    if(maxvol<n){
        return;
    }
    //剩余最小表面积加现有表面积大于已有最小表面积
    int minsurf = surf;
    for(int i = 1;i<=layer;i++){
        minsurf += i*i*i;
    }
    if(minsurf>ans){
        return;
    }
    //递归搜索
    for(int h = layer;h<=maxh;h++){
        for(int r = layer;r<=maxr;r++){
            if(layer == m){
                surf += r*r;
            }
            st.push({h,r});
            dfs(surf + 2*h*r, volume - h*r*r, layer - 1);
            st.pop();
            if(layer == m){
                surf -= r*r;
            }
        }
    }
    return;
}

int main(void)
{
    cin>>n>>m;
    //判断初始最大高度和半径
    int lim = n;
    for(int i = 1;i<m;i++){
        lim -= i*i*i;
    }
    if(lim < m*m*m){
        cout<<0<<endl;
        return 0;
    }
    st.push({lim/m/m + 1,int(sqrt(lim/m)) + 1});
    dfs(0,n,m);
    if(ans == INT32_MAX){
        cout<<0<<endl;
    }
    else{
        cout<<ans<<endl;
    }
    return 0;
}
2023/3/20 16:48
加载中...