Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

深搜+剪枝

Posted by unshakable at 2017-04-05 21:45:12 on Problem 1190
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator