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;
}
