因为题目当中的k比较小k <= 10，所以可以直接枚举，题目里面由两个trick， 一个是如果每个点都可以放稻草人的话，那么答案是0, 另外一个就是如果可以放稻草人的点不用被照到。知道了这两个基本上暴力既可以ac了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 55; struct Point { int x, y; int r; }p[maxn]; bool vis[maxn][maxn]; int cnt; bool vis2[maxn][maxn]; bool judge(int n, int k, int num) { memset(vis, false, sizeof(vis)); cnt = 0; for (int i = 0; i < k; i++) if ((1 << i) & num) cnt++; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (vis2[i][j]) continue; for (int q = 0; q < k; q++) { if ((1 << q) & num) { if (abs(p[q + 1].x - i) + abs(p[q + 1].y - j) <= p[q + 1].r) { vis[i][j] = true; break; } } } if (!vis[i][j]) return false; } } return true; } int main() { int n, k; while (~scanf("%d", &n) && n) { memset(vis2, false, sizeof(vis2)); scanf("%d", &k); for (int i = 1; i <= k; i++) scanf("%d %d", &p[i].x, &p[i].y); for (int i = 1; i <= k; i++) scanf("%d", &p[i].r); for (int i = 1; i <= k; i++) vis2[p[i].x][p[i].y] = true; bool flag = true; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (!vis2[i][j]) { flag = false; break; } } if (flag) { printf("0 "); continue; } int ans = 15000; int maxx = (1 << k); for (int i = 1; i < maxx; i++) { if (judge(n, k, i)) { ans = min(ans, cnt); } } if (ans > 10) puts("-1"); else printf("%d ", ans); } return 0; }