ABC D求调(只要能过样例就行了
查看原帖
ABC D求调(只要能过样例就行了
902351
Little_x_starTYJ楼主2024/3/16 21:48
#include <bits/stdc++.h>
using namespace std;
int n, h, w;
struct node {
	int num;
	bool b[11][11];
	int k;
};
struct notd {
	int x, y;
}a[114];
bool cmp(notd a, notd b) {
	if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}
queue<node> q;
void bfs() {
	q.push({0, {0}, h * w});
	while (!q.empty()) {
		node t = q.front();
		q.pop();
		if (t.k == 0) {
			puts("Yes");
			exit(0);
		}
		for (int i = t.num + 1; i <= n; i++) {
			if (t.k - a[i].x * a[i].y >= a[i].x * a[i].y) {
				node t2 = t;
				for (int j = 1; j <= h; j++) {
					for (int k = 1; k <= w; k++) {
						if (t2.b[j][k] == 0 && j + a[i].x <= h && 
						k + a[i].y <= w) {
							node t3 = t2;
							bool flag = 0;
							for (int l = j; l <= j + a[i].x; l++) {
								if (flag)
									break;
								for (int z = k; z <= k + a[i].y; z++) {
									if (t3.b[l][z]) {
										flag = 1; break;
									}
									t3.b[l][z] = 1;
								}
							}
							if (!flag) {
								t3.num = i;
								t3.k = t.k - a[i].x * a[i].y;
								q.push(t3);	
							}
						}
						if (t2.b[j][k] == 0 && j + a[i].y <= h && 
						k + a[i].x <= w && a[i].x != a[i].y) {
							node t3 = t2;
							bool flag = 0;
							for (int l = j; l <= j + a[i].y; l++) {
								if (flag)
									break;
								for (int z = k; z <= k + a[i].x; z++) {
									if (t3.b[l][z]) {
										flag = 1; break;
									}
									t3.b[l][z] = 1;
								}
							}
							if (!flag) {
								t3.num = i;
								t3.k = t.k - a[i].x * a[i].y;
								q.push(t3);	
							}
						}
					}
				}
			}else break;
		}
	}
	puts("No");
}
int main() {
	cin >> n >> h >> w;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	sort(a + 1, a + 1 + n, cmp);
	bfs();
	return 0;
}
2024/3/16 21:48
加载中...