一：（HDU 1045）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1045
题目是让你求给定图中如何放置大炮，使得可放置的大炮数目最多，并求出最多的大炮数目。其中大炮可横向和竖向攻击。
写这道题主要是因为这道题运用新的方法。采用了坐标标号化、即不再向以往的那样对坐标进行搜索，而是将坐标转化为标号，搜索标号了。转换方法（坐标从（0，0）开始x=number/num, y=number%num;number即该坐标编号）。而递归边界的判断也转化为了编号越界的判断。仔细想想也真他妈是个好方法、至少对ACM新人来说。
该题代码：
//使用数据单元格存储（以前用坐标）便于计算一开始不知道的情况。 #include<cstdio> #include<iostream> using namespace std; #define N 4 char map[N][N]; int maxnum,num; int if_load(int x,int y)//判断在 x行和 y列能否放置大炮 { for(int i=x-1;i>=0;i--) { if(map[i][y]=='o') return 0; if(map[i][y]=='X') break;//注意这里，并没有判断完！ } for(int i=y-1;i>=0;i--) { if(map[x][i]=='o') return 0; if(map[x][i]=='X') break; } return 1; } void dfs(int number,int cur) { if(number==num*num)//地图一轮判断完毕 { if(cur>maxnum){ maxnum=cur; return; }//是否有更大的放置?(这里的采用及其巧妙) } else { int x=number/num, y=number%num;//将单元格转换为坐标（这个一定要掌握） if(map[x][y]=='.' && if_load(x,y)) { map[x][y]='o'; dfs(number+1,cur+1); map[x][y]='.';//注意恢复以便下一次查找 } dfs(number+1,cur);//本单元格不放置大炮 } } int main() { freopen("huisu.in","r",stdin); freopen("huisu.out","w",stdout); while(scanf("%d",&num)!=EOF && num) { for(int i=0;i<num;i++) for(int j=0;j<num;j++) cin>>map[i][j]; maxnum=0; dfs(0,0); printf("%d/n",maxnum); } return 0; }
二：（HDU 1455）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1455 http://poj.org/problem?id=1011。
题目大意是有一些等长的木棍，被切成一些已知长度的小木棍（最大不超过50，这个条件也很重要）。求最小可能原长。
做这个题目的关键在与剪枝。有大妞说DFS不难，关键在于剪枝，从这道题目里面我深有体会。同样的代码在HDU上能AC，拿到PKU就超时，后来想了老久才想出一个优化，最终在PKU上也AC了。不容易啊！另外这也是一道DFS函数定义为bool类型最典型的题目。
首先能想到的优化就是一个木棍一个木棍的完成，比起一根一根的添，节省了好多不必要的判断。其次我们还会想到先求处长木棍的可能长度都有哪些，我们只枚举这些长度即可。再次题目时要求我们求最小的，那么我们就从最小的可能长度开始枚举，这样一来，有会发现一个优化，那就是将所有的短木棍从大到小先排个序，这样又能加快判断。能想到的也就这么多了，果然这样写出的代码拿到HDU上15msAC。然而这样的代码在PKU上却是TLE。我们发现数据中的短木棍有大小相同的木棍，如果这根木棍添加没有成功的话，那么和它相同的那根显然也不能成功。就像上面第一道题一样。这样优化后PKU上就轻松AC了。
下面是代码：
//这道题新颖之处在于打破常态第一次遇到dfs函数为bool类型 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 65 int num,value,group,sum,arr[N]; bool vis[N]; bool cmp(int a,int b) { return a > b; } //cursum为当前填充的木棍的长度、cur为当前用来填充的零件木棍、curgroup当前填充好了几组 bool dfs(int cursum,int cur,int curgroup) { if(curgroup==group) return true;//全部填好了！ else if(cursum==value) return dfs(0,0,curgroup+1);//填充好了一组，继续递归！注意与上一个if的顺序 else { int i,pre=0; for(i=cur;i<num;i++)//从当前木棍开始一个一个填充 if(!vis[i] && arr[i]!=pre && cursum+arr[i]<=value)//arr[i]!=pre这是一个优化（没这个POJ过不了） { pre=arr[i]; vis[i]=true; if(dfs(cursum+arr[i],i+1,curgroup)) break;//搜索下一根木棍 vis[i]=false; if(cur==0) return false;//退到了第一根木棍都没成功则该方案一定不成功 } if(i==num) return false;//木棍的编号为【0,n-1】都搜索到num了显然不成功！ else return true;//这里i一定为num-1。 } } int main() { //freopen("dfs.in","r",stdin); freopen("dfs.out","w",stdout); while(scanf("%d",&num) && num) { sum=0; for(int i=0;i<num;i++) { scanf("%d",&arr[i]); sum+=arr[i]; } sort(arr,arr+num,cmp);//优化。 for(value=arr[0];value<=sum;value++)//木棍最短为零散木棍的最大值！ if(sum%value==0)//这样长度的木棍是否满足分组 { group=sum/value;//可分组数 memset(vis,false,sizeof(vis)); if(dfs(0,0,0)) break;//我们从长度最小的木棍开始枚举，当出现第一个符合条件的木棍时搜索即可结束 } printf("%d/n",value); } return 0; }
三：（HDU 1010）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1010。
本来是一道好题，被HDU整成SB了。现在咋改都不过，我还在纠结要不要写这个题。这题不看题解估计新手很难AC，至少我不知道什么奇偶剪枝。这题的两个重要剪枝是先BFS判断最短是能不能逃生，若最短都逃不了，那就怎么都逃不了。其次就是奇偶剪枝，每走一步都判断其最短路能不能逃生（即是否偶数）。有了这两个剪枝，这题就可以了（以前可以了）。
奇偶剪枝：任意时刻，abs(ex-x)+abs(ey-y)都表示当前点p和逃生点ep之间的二维距离，可以证明，这时当前点p到逃生点ep之间的最短距离！记此最短距离长度为s。如果，此最短距离上有一些障碍物不能走，那么移动会偏移最短距离s，但是不管偏移几个点，偏移的距离都是最短距离s加上一个偶数距离。
代码如下：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; int row,column,t,cur,si,sj,di,dj,wall; int direction[5][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}}; char map[10][10]; bool escape; void getin() { for(int i=0;i<row;i++) for(int j=0;j<column;j++) { cin>>map[i][j];//巧妙地使用cin避免好多麻烦！ if(map[i][j]=='S') { si=i; sj=j; } else if(map[i][j]=='D') { di=i; dj=j; } else if(map[i][j]=='X') wall++; } } void dfs(int si,int sj,int cur) { int i,temp; if(si>row-1||sj>column-1||si<0||sj<0) return; if(cur==t && si==di &&sj==dj) escape=true; if(escape) return; temp=(t-cur)-abs(si-di)-abs(sj-dj); if(temp<0||temp&1) return;//奇偶剪枝temp&1为0则temp为偶数，否则为奇数。 for(int i=1;i<=4;i++) { si+=direction[i][0]; sj+=direction[i][1]; if(map[si][sj]!='X')//注意这里！不能写成map[si][sj]=='.'为什么？ { map[si][sj]='X'; dfs(si,sj,cur+1); map[si][sj]='.'; } si-=direction[i][0]; sj-=direction[i][1]; } return; } int main() { freopen("dfs.in","r",stdin); freopen("dfs.out","w",stdout); while(scanf("%d%d%d",&row,&column,&t)!=EOF) { if(row==0 && column==0 &&t==0) break; wall=0; getin(); if(row*column-wall<=t){ printf("NO/n"); continue; } escape=false; map[si][sj]='X'; dfs(si,sj,0); if(escape) printf("YES/n"); else printf("NO/n"); } return 0; }
