hdu 4462 Scaring the Birds(STL)

本文主要是介绍hdu 4462 Scaring the Birds(STL)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4462 Scaring the Birds

题目大意：给定N，表示有一个N∗N的农田，现在有些位置的谷物已经被毁坏，农场主决定在这些位置中选择一些放

置稻草人，给定每个点放置稻草人可以覆盖的曼哈顿距离。求最少放多少个稻草人。

解题思路：题意需要注意，可以放稻草人的位置是没有谷物的。然后对于每个位置预处理出可以覆盖的位置，用bitset

优化即可。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <bitset>
#include <algorithm>using namespace std;
const int maxn = 55;
const int maxm = 15;
const int inf = 0x3f3f3f3f;bitset<maxn * maxn> s, p[maxm];int N, K, R[maxm], C[maxm], D[maxm];
int g[maxn][maxn];void init () {memset(g, 0, sizeof(g));scanf("%d", &K);for (int i = 0; i < K; i++) {scanf("%d%d", &R[i], &C[i]);g[R[i]][C[i]] = 1;}for (int i = 0; i < K; i++)scanf("%d", &D[i]);for (int i = 0; i < K; i++) {p[i].reset();for (int x = 1; x <= N; x++) {for (int y = 1; y <= N; y++) {if (g[x][y])continue;if (abs(x - R[i]) + abs(y - C[i]) <= D[i])p[i].set( (x-1) * N + y-1);}}}
}int solve() {int ans = inf;for (int i = 0; i < (1<<K); i++) {int cnt = 0;s.reset();for (int j = 0; j < K; j++) {if (i&(1<<j)) {cnt++;s |= p[j];}}if (s.count() == N * N - K)ans = min(ans, cnt);}return ans == inf ? -1 : ans;
}int main () {while (scanf("%d", &N) == 1 && N) {init();printf("%d\n", solve());}return 0;
}

这篇关于hdu 4462 Scaring the Birds(STL)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---