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

AC奉上

Posted by lzy_Dennis at 2023-09-12 19:54:10 on Problem 1190
#include<iostream>
#include<cmath>
#include<cstdio>
#include<string>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int N, M;
int min_s = 0x7fffffff;
inline int min_v(int m) {
	int v = 0;
	for (int R = M - m; R >= 1; R--) {
		int H = R;
		v += R * R * H;
	}
	return v;
}

inline int max_v(int r, int h, int m) {
	int v = 0;
	for (int R = r, H = h; m <= M; R--, H--,m++) {
		v += R * R * H;
	}
	return v;
}
inline void dfs(int r, int h, int m, int s, int v) {
	if (m == M && N == v && s < min_s) {
		min_s = s;
		return;
	}
	if (r == 0 || s + 2 * (N - v) / r > min_s)
		return;
	if (min_v(m) > N - v)
		return;
	if (max_v(r, h, m) < N - v)
		return;
	for (int R = r - 1; R >= M - m; R--)
		for (int H = h - 1; H >= M - m; H--) {
			dfs(R, H, m + 1, s + 2 * R * H, v + R * R * H);
		}
}
int main() {
	scanf("%d%d", &N, &M);
	for (int r1 = M; r1 * r1 <= N; r1++)
		for (int h1 = N / (r1 * r1); h1 >= M; h1--) {
			int s = r1 * r1 + r1 * h1 * 2;
			int v = r1 * r1 * h1;
			dfs(r1, h1, 1, s, v);
		}
	if (min_s == 0x7fffffff)
		cout << 0 << endl;
	else
		cout << min_s << 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