1 solutions

  • 0
    @ 2024-8-28 23:40:15
    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 25, inf = 1 << 30;
    
    int minv[N], mins[N];
    int h[N], r[N];
    int n, m, ans = 1 << 30;
    
    void dfs(int dep, int v, int s) { // 处理完的体积和处理完的体积
        if(v + minv[dep] > n) return;
        if(s + mins[dep] >= ans) return;
        if(s + 2 * (n - v) / r[dep + 1] >= ans) return;
        if(!dep) {
            if(v == n) ans = s;
            return;
        }
        //枚举dep层了
        for(int R = min(r[dep + 1] - 1, (int)sqrt((n - v - minv[dep - 1]) / dep)); R >= dep; R -- )
            for(int H = min(h[dep + 1] - 1, (n - v - minv[dep - 1]) / R / R); H >= dep; H -- ){
                h[dep] = H, r[dep] = R;
                int t = dep == m ? R * R : 0;
                dfs(dep - 1, v + R * R * H, s + 2 * R * H + t);
            }
    }
    
    int main() {
        cin >> n >> m;
        for(int i = 1; i <= m; i ++ ) {
            minv[i] = minv[i - 1] + i * i * i;
            mins[i] = mins[i - 1] + i * i * 2;
        }
        h[m + 1] = r[m + 1] = inf;
        dfs(m, 0, 0);
        if(ans == inf) ans = 0;
        cout << ans << endl;
        return 0;
    }
    
    • 1

    Information

    ID
    485
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    1
    Accepted
    1
    Uploaded By