学步园

一：（HDU 1045）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1045

题目是让你求给定图中如何放置大炮，使得可放置的大炮数目最多，并求出最多的大炮数目。其中大炮可横向和竖向攻击。

         写这道题主要是因为这道题运用新的方法。采用了坐标标号化、即不再向以往的那样对坐标进行搜索，而是将坐标转化为标号，搜索标号了。转换方法（坐标从（0，0）开始x=number/num, y=number%num;number即该坐标编号）。而递归边界的判断也转化为了编号越界的判断。仔细想想也真他妈是个好方法、至少对ACM新人来说。

该题代码：

//使用数据单元格存储（以前用坐标）便于计算一开始不知道的情况。<br /> #include<cstdio><br /> #include<iostream><br /> using namespace std;<br /> #define N 4</p> <p>char map[N][N];<br /> int maxnum,num;</p> <p>int if_load(int x,int y)//判断在 x行和 y列能否放置大炮<br /> {<br /> for(int i=x-1;i>=0;i--)<br /> {<br /> if(map[i][y]=='o') return 0;<br /> if(map[i][y]=='X') break;//注意这里，并没有判断完！<br /> }<br /> for(int i=y-1;i>=0;i--)<br /> {<br /> if(map[x][i]=='o') return 0;<br /> if(map[x][i]=='X') break;<br /> }<br /> return 1;<br /> }</p> <p>void dfs(int number,int cur)<br /> {<br /> if(number==num*num)//地图一轮判断完毕<br /> {<br /> if(cur>maxnum){ maxnum=cur; return; }//是否有更大的放置?(这里的采用及其巧妙)<br /> }<br /> else<br /> {<br /> int x=number/num, y=number%num;//将单元格转换为坐标（这个一定要掌握）<br /> if(map[x][y]=='.' && if_load(x,y))<br /> {<br /> map[x][y]='o'; dfs(number+1,cur+1); map[x][y]='.';//注意恢复以便下一次查找<br /> }<br /> dfs(number+1,cur);//本单元格不放置大炮<br /> }<br /> }</p> <p>int main()<br /> {<br /> freopen("huisu.in","r",stdin); freopen("huisu.out","w",stdout);<br /> while(scanf("%d",&num)!=EOF && num)<br /> {<br /> for(int i=0;i<num;i++)<br /> for(int j=0;j<num;j++) cin>>map[i][j];<br /> maxnum=0;<br /> dfs(0,0);<br /> printf("%d/n",maxnum);<br /> }<br /> return 0;<br /> }</p> <p>

二：（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类型<br /> #include<cstdio><br /> #include<cstring><br /> #include<algorithm><br /> using namespace std;<br /> #define N 65</p> <p>int num,value,group,sum,arr[N];<br /> bool vis[N];</p> <p>bool cmp(int a,int b)<br /> {<br /> return a > b;<br /> }</p> <p>//cursum为当前填充的木棍的长度、cur为当前用来填充的零件木棍、curgroup当前填充好了几组<br /> bool dfs(int cursum,int cur,int curgroup)<br /> {<br /> if(curgroup==group) return true;//全部填好了！<br /> else if(cursum==value) return dfs(0,0,curgroup+1);//填充好了一组，继续递归！注意与上一个if的顺序<br /> else<br /> {<br /> int i,pre=0;<br /> for(i=cur;i<num;i++)//从当前木棍开始一个一个填充<br /> if(!vis[i] && arr[i]!=pre && cursum+arr[i]<=value)//arr[i]!=pre这是一个优化（没这个POJ过不了）<br /> {<br /> pre=arr[i]; vis[i]=true;<br /> if(dfs(cursum+arr[i],i+1,curgroup)) break;//搜索下一根木棍<br /> vis[i]=false;<br /> if(cur==0) return false;//退到了第一根木棍都没成功则该方案一定不成功<br /> }<br /> if(i==num) return false;//木棍的编号为【0,n-1】都搜索到num了显然不成功！<br /> else return true;//这里i一定为num-1。<br /> }<br /> }</p> <p>int main()<br /> {<br /> //freopen("dfs.in","r",stdin); freopen("dfs.out","w",stdout);<br /> while(scanf("%d",&num) && num)<br /> {<br /> sum=0;<br /> for(int i=0;i<num;i++)<br /> {<br /> scanf("%d",&arr[i]);<br /> sum+=arr[i];<br /> }<br /> sort(arr,arr+num,cmp);//优化。<br /> for(value=arr[0];value<=sum;value++)//木棍最短为零散木棍的最大值！<br /> if(sum%value==0)//这样长度的木棍是否满足分组<br /> {<br /> group=sum/value;//可分组数<br /> memset(vis,false,sizeof(vis));<br /> if(dfs(0,0,0)) break;//我们从长度最小的木棍开始枚举，当出现第一个符合条件的木棍时搜索即可结束<br /> }<br /> printf("%d/n",value);<br /> }<br /> return 0;<br /> }<br />

三：（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><br /> #include<iostream><br /> #include<algorithm><br /> #include<cstring><br /> #include<cstdlib><br /> #include<cmath><br /> using namespace std;</p> <p>int row,column,t,cur,si,sj,di,dj,wall;<br /> int direction[5][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};<br /> char map[10][10];<br /> bool escape;</p> <p>void getin()<br /> {<br /> for(int i=0;i<row;i++)<br /> for(int j=0;j<column;j++)<br /> {<br /> cin>>map[i][j];//巧妙地使用cin避免好多麻烦！<br /> if(map[i][j]=='S') { si=i; sj=j; }<br /> else if(map[i][j]=='D') { di=i; dj=j; }<br /> else if(map[i][j]=='X') wall++;<br /> }<br /> }</p> <p>void dfs(int si,int sj,int cur)<br /> {<br /> int i,temp;<br /> if(si>row-1||sj>column-1||si<0||sj<0) return;<br /> if(cur==t && si==di &&sj==dj) escape=true;<br /> if(escape) return;<br /> temp=(t-cur)-abs(si-di)-abs(sj-dj);<br /> if(temp<0||temp&1) return;//奇偶剪枝temp&1为0则temp为偶数，否则为奇数。<br /> for(int i=1;i<=4;i++)<br /> {<br /> si+=direction[i][0]; sj+=direction[i][1];<br /> if(map[si][sj]!='X')//注意这里！不能写成map[si][sj]=='.'为什么？<br /> {<br /> map[si][sj]='X'; dfs(si,sj,cur+1); map[si][sj]='.';<br /> }<br /> si-=direction[i][0]; sj-=direction[i][1];<br /> }<br /> return;<br /> }</p> <p>int main()<br /> {<br /> freopen("dfs.in","r",stdin); freopen("dfs.out","w",stdout);<br /> while(scanf("%d%d%d",&row,&column,&t)!=EOF)<br /> {<br /> if(row==0 && column==0 &&t==0) break;<br /> wall=0;<br /> getin();<br /> if(row*column-wall<=t){ printf("NO/n"); continue; }<br /> escape=false; map[si][sj]='X'; dfs(si,sj,0);<br /> if(escape) printf("YES/n");<br /> else printf("NO/n");<br /> }<br /> return 0;<br /> }</p> <p>