OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2005】互不侵犯

【题目描述】

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

【输入】

只有一行,包含两个数N,K。

【输出】

方案数。

【输入样例】

3 2

【输出样例】

16

【数据范围】

1<=N<=9,0<=K<=N*N

【题解】

还是先DFS预处理每一行合法的放置(我还是偷懒枚举的二进制数QAQ),顺路就可以计算出这一排每种方案的放置数,然后就放心大胆的DP就好。

状态转移方程如下:

f[i][j][t]=Σf[i-1][j'][t-sum[j]]

其中f[i][j][t]表示当第i行放置方案为j,放置棋子总数为k时,放置的总方案数,最后统计f[n][i][k](i∈U)的总数就是答案。

【代码】

如果预先处理了每种方案的放置数,几乎是秒过~

http://paste.ubuntu.com/7260060/

评论

© OI技术宅 | Powered by LOFTER