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