注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4529 郑厂长系列故事——N骑士问题  

2014-03-28 11:08:21|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4529
在8*8的八皇后棋盘上,问最多放n个骑士的方案数,任意两个骑士不受攻击,骑士“日”字走法。
解法:
看完题就想到状态压缩dp了,但是之前没怎么练过,状态转移方程没写出来。
上网看了几道经典例题,炮兵阵法,棋盘摆放棋子等,慢慢理解了状压dp,状态转移方程自然就写出来了。
因为骑士走的是“日”字格,所以关联到前两行的状态,这道题棋子个数还有限制,所以可以用f[i][j][p][q]来建立模型,表示第 i 行用了 j 个棋子,第 i 行是 p 状态,第 i - 1 行是 q 状态的最大方案数。
所以复杂度为8*10*(1<<7)*(1<<7)*(1<<7),如果不剪枝肯定超时,仔细分析下有很多种情况都是不可行的。
打完后调了一个小bug,很顺利过了样例,结果TLE,继续加优化,还是TLE,最后用vis[i][p][q]标记第i行p状态,第i-1行q状态是否可行,终于过了,2702ms过的,好险。。

char c[10][10];
int n,f[10][12][130][130]; //f[i][j][p][q] 第i行,j个棋子数,i行p状态,i-1行q状态
int huang[10],qinum[130],s[3][10]; //huang记录每行皇后的位置
int vis[10][130][130]; //vis[i][p][q], 第i行p状态,第i-1行q状态下,是否可行

int Getqizi(int a) //统计a状态有多少个1
{
int tmp=0;
while(a)
{
if(a&1)
tmp++;
a>>=1;
}
return tmp;
}

void init() //每种状态多少个1,打表处理
{
for(int i=0;i<128;i++)
qinum[i]=Getqizi(i);
}

void deal(int c,int p,int t) //第c行的p状态映射到s[t]上
{
MEM(s[t]);
int tt=0;
while(p)
{
if(tt == huang[c]) //皇后的位置跳过
s[t][tt++]=-1;
s[t][tt++]=p%2;
p>>=1;
}
}

int jud1(int t) //判断相邻两行是否符合条件
{
for(int i=0;i<8;i++)
if(s[t][i] == 1)
{
if(i-2 >= 0 && s[t+1][i-2] == 1)
return 0;
if(i+2 < 8 && s[t+1][i+2] == 1)
return 0;
}
return 1;
}

int jud2() //判断隔一行是否符合条件
{
for(int i=0;i<8;i++)
if(s[0][i] == 1)
{
if(i-1 >= 0 && s[2][i-1] == 1)
return 0;
if(i+1 < 8 && s[2][i+1] == 1)
return 0;
}
return 1;
}

void solve()
{
MEM(f);memset(vis,-1,sizeof(vis));
for(int i=0;i<128;i++) //预处理第一行
{
f[0][qinum[i]][i][0]++;
}
for(int i=1;i<8;i++) //行数
{
for(int j=0;j<=n;j++) //棋子数
{
for(int p=0;p<128;p++) //枚举第i行的状态
{
int num1=qinum[p];
if(num1 > j) //如果当前棋子数超出范围则不用继续,下面也一样
continue;
deal(i,p,0);
for(int q=0;q<128;q++) //枚举第i-1行的状态
{
int num2=qinum[q];
if(num1+num2 > n)
continue;
deal(i-1,q,1);
if(vis[i][p][q] == -1)
vis[i][p][q]=jud1(0);
if(vis[i][p][q] == 0)
continue;
if(i == 1) //如果是第1行,则不用执行下面的判断
{
f[i][j][p][q]+=f[i-1][j-num1][q][0];
continue;
}
for(int k=0;k<128;k++) //枚举第i-2行状态
{
int num3=qinum[k];
if(num1+num2+num3 > n)
continue;
deal(i-2,k,2);
if(vis[i-1][q][k] == 0 || !jud2())
continue;
f[i][j][p][q]+=f[i-1][j-num1][q][k];
}
}
}
}
}
LL ans=0;
for(int i=0;i<128;i++)
for(int j=0;j<128;j++)
ans+=f[7][n][i][j];
pf64(ans);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int T;
sf(T);
init();
while(T--)
{
sf(n);
fr(8) sfs(c[i]);
//记录每行皇后位置
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
if(c[i][j] == '*')
{
huang[i]=j;
break;
}
}
}
solve();
}
return 0;
}



  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017