HDU 4462 Scaring the Birds （状态压缩 暴搞）
题意：给定了一个N*N的地图，地图上有K（0--10）个点可以放守卫，其它点有食物，每个守卫有一个R，只要其它点的食物到守卫点的曼哈顿距离在R范围内就算被保护。
问最少需要多少个守卫，使得所有食物都被保护。
看到K最多只有10，就可以状态压缩K的所有情况，枚举一遍，可行就比较一下。
有个trick：只需要所有的食物被保护就行，空地如果不放守卫未被保护也可以。
#include <iostream>#include <algorithm>#include <cmath>#include<functional>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <set>#include <queue>#include <stack>#include <climits>//形如INT_MAX一类的#define MAX 100005#define INF 0x7FFFFFFFusing namespace std;int n,k,ans;int buff[1 << 10];int vis[55][55];int mp[55][55];int dir1[] = {1,1,-1,-1};int dir2[] = {1,-1,-1,1};struct node { int x,y; int r;} pos[11];bool inside(int x,int y) { if(x > 0 && x <= n && y > 0 && y <= n) return 1; return 0;}void cover(int id) { int x = pos[id].x; int y = pos[id].y; int r = pos[id].r; for(int dx=0; dx<=r; dx++) { for(int dy=0; dy<=r-dx; dy++) { for(int i=0; i<4; i++) { int xx = x + dir1[i] * dx; int yy = y + dir2[i] * dy; if(inside(xx,yy)) vis[xx][yy] = 1; } } }}bool judge() { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(vis[i][j] == 0 && mp[i][j] == 0) return 0; } } return 1;}void solve() { int total = 1 << k; for(int i=0; i<total; i++) { memset(vis,0,sizeof(vis)); int tmp = i; int cnt = 0; int num = 0; while(tmp) { if(tmp & 1) { num ++; cover(cnt); } tmp = tmp >> 1; cnt ++; } if(judge()) { ans = min(ans,num); } } if(ans == INF) printf("-1\n"); else printf("%d\n",ans);}int main() { while(scanf("%d",&n) && n) { scanf("%d",&k); memset(mp,0,sizeof(mp)); for(int i=0; i<k; i++) { scanf("%d%d",&pos[i].x,&pos[i].y); mp[pos[i].x][pos[i].y] = 1; } for(int i=0; i<k; i++) { scanf("%d",&pos[i].r); } ans = INF; solve(); } return 0;}