| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
深搜+剪枝#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int N, M;
int minArea = 1 << 30;
int area = 0;
int minV[24]; //剩下层数需要的体积,从剩下1层到剩下M-1层
void dfs(int volume, int num, int radius, int height) //体积,层数,半径,高
{
if (num == 0) { //n = 0,搜索结束
if (volume) return;
else {
minArea = min(minArea, area);
return;
}
}
if (volume <= 0) return;
for (int rr = radius; rr >= num; rr--) {
if (num == M) area = rr*rr;
for (int hh = height; hh >= num; hh--) {
if (area + 2 * rr*hh >= minArea) continue;
if (volume - rr*rr*hh < minV[num - 1]) continue;
if (rr - num + 1 <= 0 || hh - num + 1 <= 0) continue;
int sum = 0;
for (int i = num - 1; i >= 0; i--)
sum += (rr - i)*(rr - i)*(hh - i);
if (sum < volume) continue;
area += 2 * rr * hh;
dfs(volume - rr*rr*hh, num - 1, rr - 1, hh - 1);
area -= 2 * rr * hh;
}
}
}
int main()
{
for (int i = 1; i < 24; i++) {
int sum = 0;
for (int j = 1; j <= i; j++)
sum += j * j * j;
minV[i] = sum;
}
cin >> N >> M;
int maxV = N, maxR, maxH;
for (int i = 1; i < M; i++)
maxV -= i*i;
maxR = maxH = sqrt(maxV);
dfs(N, M, maxR, maxH);
if (minArea == (1 << 30))
minArea = 0;
cout << minArea << endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator