学步园

分析：此题实在是看不出什么算法，只好爆搜了，但是算一下时间复杂度必然超时，于是有必要做强大的剪枝。。。

          以下摘自某牛博客：http://hi.baidu.com/billdu/blog/item/e24439a5ca9efae29052ee87.html

          首先注意这样一个事情：地毯越大越好。放大地毯的话，由于可以地毯之间覆盖，是没有任何损失的。所以说先用一个动态规划求出来以每个格子为左上角的正方形地毯最大能有多大（转移方程 f[i][j] = min(f[i + 1][j], f[i][j + 1], f[i + 1][j + 1]) + 1，如果(i, j)不能盖住则f[i][j] = 0）。这样我们就得到了W * H个正方形。之后进一步扫描，如果某个正方形被另外的正方形完全包含就把它删掉，这样能进一步减少可行正方形方案的数量。

然后预处理一张表，看看需要被覆盖的格子用哪些正方形可以盖住。

之后就变成了这样一个问题：

从一些正方形中选取最少数量的正方形，使得所有的要被盖住的格子都被盖住。

这样的问题有一个一般情况下非常精准的估价函数：首先将计数器清零。之后扫描每一个格子，如果没有被盖住，就先将计数器加一，然后将所有能将其覆盖的正方形全覆盖上去。循环往复，最后返回计数器的值。

此函数的相容性显然。用上这个，此题就可以0MS过掉了~~

可是我还是没0ms，囧~~~我又水了

贴下代码：

#include <stdio.h><br /> #include <vector><br /> using namespace std;<br /> bool map[10][10],p[100];<br /> char f[10][10],g[100][2];<br /> vector<char>d[10][10];<br /> int n,m,ans,t;<br /> inline int min(int a,int b)<br /> {<br /> return a<b?a:b;<br /> }<br /> inline int fun()<br /> {<br /> int tot=0,i,j,k;<br /> bool q[100];<br /> for(i=0;i<t;++i)q[i]=p[i];<br /> for(i=0;i<n;++i)<br /> for(j=0;j<m;++j)<br /> if(map[i][j])<br /> {<br /> for(k=0;k<d[i][j].size();++k)<br /> if(q[d[i][j][k]])break;<br /> if(k==d[i][j].size())<br /> {<br /> ++tot;<br /> for(k=0;k<d[i][j].size();++k)q[d[i][j][k]]=1;<br /> }<br /> }<br /> return tot;<br /> }<br /> void dfs(int x,int y,int now)<br /> {<br /> if(now+fun()>=ans)return;<br /> if(y==m)y=0,++x;<br /> if(x==n)<br /> {<br /> ans=now;<br /> return;<br /> }<br /> bool cover=0;<br /> for(int k=0;k<d[x][y].size();++k)<br /> if(p[d[x][y][k]])<br /> {<br /> cover=1;<br /> break;<br /> }<br /> if(map[x][y]==0||cover)<br /> {<br /> dfs(x,y+1,now);<br /> return;<br /> }<br /> for(int k=0;k<d[x][y].size();++k)<br /> {<br /> p[d[x][y][k]]=1;<br /> dfs(x,y+1,now+1);<br /> p[d[x][y][k]]=0;<br /> }<br /> }<br /> int main(int argc, char* argv[])<br /> {<br /> int i,j,k,l;<br /> while(scanf("%d %d",&m,&n),n)<br /> {<br /> for(i=0; i<n; ++i)<br /> for(j=0; j<m; ++j)<br /> scanf("%d",&k),map[i][j]=f[i][j]=k;<br /> for(i=n-2; i>=0; --i)<br /> for(j=m-2; j>=0; --j)<br /> if(map[i][j])f[i][j]=min(f[i+1][j],min(f[i][j+1],f[i+1][j+1]))+1;<br /> t=0;<br /> for(i=0; i<n; ++i)<br /> for(j=0; j<m; ++j)<br /> {<br /> for(k=0; k<=i; ++k)<br /> for(l=0; l<=j; ++l)<br /> {<br /> if(k==i&&l==j)continue;<br /> if(i+f[i][j]<=k+f[k][l]&&j+f[i][j]<=l+f[k][l])f[i][j]=0;<br /> }<br /> if(f[i][j]>0)g[t][0]=i,g[t][1]=j,++t;<br /> }<br /> for(i=0; i<n; ++i)<br /> for(j=0; j<m; ++j)<br /> {<br /> d[i][j].clear();<br /> if(map[i][j])<br /> for(k=0;k<t;++k)<br /> if(g[k][0]<=i&&g[k][1]<=j&&g[k][0]+f[g[k][0]][g[k][1]]>i&&g[k][1]+f[g[k][0]][g[k][1]]>j)d[i][j].push_back(k);<br /> }<br /> ans=m*n;<br /> dfs(0,0,0);<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }