2012 Asia Hangzhou Regional Contest--hdu4462Scaring the Birds(IDA)
题目请戳这里
题目大意：
有一个n*n的格子，有k个空地，其他地方都种的有庄稼。现在要在k个空地中放稻草人保护庄稼，每个稻草人罩附近距离他曼哈顿距离不超过r的点，求最少需要多少个稻草人能罩住所有的庄稼。
题目分析：k太小了，n太小了，IDA爆搜之。
不过跑的好慢啊，hdu rank倒数第一。。。
详情请见代码：
#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<cctype>#include<map>#include<vector>#include<set>#include<queue>#include<string>#include<ctime>using namespace std;const int N = 51;const int M = 10000005;const int inf = 0x3f3f3f3f;const double eps = 1e-6;const double PI = acos(-1.0);typedef __int64 ll;int flag[N][N];bool used[N];struct node{ int x,y,r;}pt[N];int n,k;int ans,corns;bool ok;int put(int id){ int i,j; int row,col; int ret = 0; row = pt[id].x - pt[id].r; if(row < 1) row = 1; for(i = row,col = pt[id].r - (pt[id].x - row);i <= pt[id].x;i ++,col ++) { int l,r; l = max(1,pt[id].y - col); r = min(n,pt[id].y + col); for(j = l;j <= r;j ++) { flag[i][j] ++; if(flag[i][j] == 1) ret ++; } } row = pt[id].x + pt[id].r; if(row > n) row = n; for(i = pt[id].x + 1,col = pt[id].r - 1;i <= row;i ++,col --) { int l,r; l = max(1,pt[id].y - col); r = min(n,pt[id].y + col); for(j = l;j <= r;j ++) { flag[i][j] ++; if(flag[i][j] == 1) ret ++; } } return ret;}void disput(int id){ int i,j; int row,col; row = pt[id].x - pt[id].r; if(row < 1) row = 1; for(i = row,col = pt[id].r - (pt[id].x - row);i <= pt[id].x;i ++,col ++) { int l,r; l = max(1,pt[id].y - col); r = min(n,pt[id].y + col); for(j = l;j <= r;j ++) { flag[i][j] --; } } row = pt[id].x + pt[id].r; if(row > n) row = n; for(i = pt[id].x + 1,col = pt[id].r - 1;i <= row;i ++,col --) { int l,r; l = max(1,pt[id].y - col); r = min(n,pt[id].y + col); for(j = l;j <= r;j ++) { flag[i][j] --; } }}void show(){ for(int i = 1;i <= n;i ++) { for(int j = 1;j <= n;j ++) printf("%4d",flag[i][j]); putchar(10); }}void dfs(int dp,int last){ if(last == 0) { ok = true; return; } //show(); if(dp >= ans) return; if(ok) return; int i; for(i = 1;i <= k;i ++) { if(used[i]) continue; used[i] = true; int tmp = put(i); dfs(dp + 1,last - tmp); disput(i); used[i] = false; }}int main(){ int i; while(scanf("%d",&n),n) { scanf("%d",&k); memset(flag,0,sizeof(flag)); for(i = 1;i <= k;i ++) { scanf("%d%d",&pt[i].x,&pt[i].y); flag[pt[i].x][pt[i].y] = inf; } for(i = 1;i <= k;i ++) scanf("%d",&pt[i].r); corns = n * n - k; if(corns <= 0) { printf("0\n"); continue; } ans = 0; ok = false; memset(used,false,sizeof(used)); while(1) { ans ++; dfs(0,corns); if(ok || ans >= k) break; } if(ok) printf("%d\n",ans); else printf("-1\n"); } return 0;}