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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1087][SCOI2005]互不侵犯King  

2015-03-16 21:25:04|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1779  Solved: 1046
[Submit][Status][Discuss]

Description

在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。

Input

只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

Output

方案数。

Sample Input

3 2

Sample Output

16

Solution

首先,我们看到n是非常小的,这就让我们想到了两种做法:搜索与状压DP。

不过由于本题中方案数可能非常多(例如n = k = 9时方案数要开long long才能存得下),所以搜索是不可行的。

我们来考虑状压DP。首先,我们可以先进行一个预处理,把本身就不合法的状态筛掉,再把可以互相转移的状态存起来(可以考虑使用邻接表)。预处理之后,我们会发现,不合法的状态被筛掉很多,而所有的转移关系最多也只有3500个左右。

我们令f[i][j][k]表示直到第i行放了j个国王,状态为k的方案数,那么转移就是

f[i][j][k] = sum(f[i][j-cnt(k)][k']),其中,cnt[k]表示k的二进制表示有几个1,k'表示可以从k'转移到k的状态。

由于转移关系很少,而不合法方案数又筛掉很多,所以4层for也可以AC。

Code

/**************************************************************
    Problem: 1087
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:16 ms
    Memory:1856 kb
****************************************************************/
 
#include<cstdio>
int n,m,k,i,j,l,et,la[512],can[100],tot,s,cnt[512];long long f[10][512][26],ans;
struct E{int to,nxt;}e[1<<10];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
#define check(x,y) ((x&y)==0&&(x&(y<<1))==0&&(x&(y>>1))==0)
int main(){
    scanf("%d%d",&n,&m);s=(1<<n)-1;
    for(i=0;i<=s;i++)if((i&(i>>1))==0)can[++tot]=i;add(0,0);
    for(i=1;i<=tot;i++)
    for(j=1;j<i;j++)if(check(can[i],can[j]))add(can[i],can[j]),add(can[j],can[i]);
    for(i=1;i<=s;i++)cnt[i]=cnt[i>>1]+(i&1);
    for(f[0][0][0]=1,i=0;i<n;i++)
    for(j=0;j<=s;j++)
    for(l=cnt[j];l<=m;l++)if(f[i][j][l])
    for(k=la[j];k;k=e[k].nxt)
    f[i+1][e[k].to][l+cnt[e[k].to]]+=f[i][j][l];
    for(i=1;i<=tot;i++)ans+=f[n][can[i]][m];
    printf("%lld\n",ans);
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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