1190 生日蛋糕 NI

dfs+剪枝

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
int N, M, S;
//const int MAXN = , MAXM = 0;
//typedef long long ll;
using namespace std;
int miarr[25];
void dfs(int leftv, int m, int cost, int prer, int preh) {
    if (cost >= S) return;
    if (m == 0) {
        if (leftv) return;
        cost += prer * prer;
        S = min(S, cost);
        return;
    }
    
    for (int h = m; h < preh; h++) {
        for (int r = m; r < prer; r++) {
            int v = leftv - r * r * h;
            int dwon = prer * prer - r * r;
            int side = 2 * r * h;
            int mx = (h - 1) * (r - 1) * (r - 1) * m;
            if (v < 0) break;
            if (mx < v) continue;//用不完
            if (v < miarr[m - 1]) break; //不够用
            int nc = cost + side;
            if (m != M) nc += dwon;
            dfs(v, m - 1, nc, r, h);
        }
    }
}
int main() {
    cin >> N >> M;
    S = 2000000000;
    for (int i = 1; i < 22; i++) miarr[i] = i * i + miarr[i - 1];
    dfs(N, M, 0, 100, 10000);
    if (S == 000000000) S = 0;
    cout << S << endl;
    return 0;
}