搜索测试题目（2）

生日快乐
本题与巧克力棒相似:
http://222.180.160.110:1024/contest/1343/problem/5
巧克力棒代码:

#include <queue>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#include <stack>
using namespace std;
int t, n, m, k, a[35][35][55];
int dfs(int x, int y, int z) {
	if (x * y < z) {
		return 1e9;
	}
	if (x * y == z || z == 0) {
		return 0;
	}
	if (a[x][y][z] != -1) {
		return a[x][y][z];
	}
	int MIN = INT_MAX;
	for (int i = 1; i <= x / 2; i++) {
		for (int j = 0; j <= z && j <= i * y; j++) {
			MIN = min(MIN, y * y + dfs(i, y, j) + dfs(x - i, y, z - j));
		}
	}
	for (int i = 1; i <= y / 2; i++) {
		for (int j = 0; j <= z && j <= x * i; j++) {
			MIN = min(MIN, x * x + dfs(x, i, j) + dfs(x, y - i, z - j));
		}
	}
	a[y][x][z] = MIN;
	return a[x][y][z] = MIN;
}
int main() {
	scanf("%d", &t);
	memset(a, -1, sizeof(a));
	for (int i = 1; i <= t; i++) {
		scanf("%d %d %d", &n, &m, &k);
		int o = dfs(n, m, k);
		printf("%d\n", o);
	}
	return 0;
}

主要是横切和竖切,并一个个搜索判断切的位置。
直接见代码......:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdlib>
using namespace std;
int x, y, n;
double dfs(double o, double p, int u) {
	if (u == 1) {
		return max(o, p) / min(o, p);
	}
	double ans = 1000007;
	for (int i = 1; i <= u / 2; i++) {
		ans = min(ans, max(dfs(o, p / u * i, i), dfs(o, p - p / u * i, u - i)));
		ans = min(ans, max(dfs(o / u * i, p, i), dfs(o - o / u * i, p, u - i)));
	}
	return ans;
}
int main() {
	freopen("birthday.in", "r", stdin);
	freopen("birthday.out", "w", stdout);
	scanf("%d %d %d", &x, &y, &n);
	printf("%.6lf", dfs(x * 1.0, y * 1.0, n));
	return 0;
}

搜索测试题目（2）

原文：https://www.cnblogs.com/cqbzljw/p/14529564.html