博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
SGU-223 Little Kings 状态压缩+DP
阅读量:5817 次
发布时间:2019-06-18

本文共 1677 字,大约阅读时间需要 5 分钟。

  这算是八皇后问题的变种了,普通的组合数学已经很难一下子将他求出来了,除此之外,我们用纯模拟来处理该题。

  给定是一个N*N的矩阵,要求在这个图中放置K个点,这些点不能够相邻(包括上下左右以及对角线上的区域),用模拟如何来过这一题呢,那就是要推出动态递归方程,F[i][s][k] 代表第i行处于第s个状态且到目前行共下了k个棋子的总方案数,c[s]代表针对s这个状态有多少个1,有动态方程:F[i][s][k] = sum{ F[i-1][s'][k-c[s]],其中 s 与 s' 为不冲突的方案数 } 该方程的含义为 F[i][s][k] 中剩余的棋子数 k-c[s] 在上一行截止时所走的总方案。

  代码如下:

#include 
#include
#include
#include
#define MAXN 150 using namespace std; int N, K, M, s[MAXN], c[MAXN]; long long f[11][MAXN][MAXN]; void dfs(int l, int state, int total) {
if (l == N) {
s[M] = state; c[M++] = total; return; // 递归就此结束 } dfs(l+1, state<<1, total); // 不管左边相邻的列是否放置,该位不放置总是行的 if (!(state&1)) dfs(l+1, state<<1|1, total+1); } bool judge(int s1, int s2) {
if (s[s1] & s[s2]) return false; if (s[s1]<<1 & s[s2]) return false; if (s[s2]<<1 & s[s1]) return false; return true; } void dp(int l, int state, int k) {
f[l][state][k] = 0; for (int i = 0; i < M; ++i) {
if (k >= c[state] && judge(i, state)) {
if (f[l-1][i][k-c[state]] == -1) dp(l-1, i, k-c[state]); f[l][state][k] += f[l-1][i][k-c[state]]; } } } int main() {
long long ans = 0; M = 0; // M 表示状态的数量 memset(f, 0xff, sizeof (f)); scanf("%d %d", &N, &K); dfs(0, 0, 0); memset(f[0], 0, sizeof (f[0])); f[0][0][0] = 1; // 中间的0代表第1种状态 for (int i = 0; i < M; ++i) {
if (f[N][i][K] == -1) { dp(N, i, K); } ans += f[N][i][K]; } cout << ans; return 0; }

转载于:https://www.cnblogs.com/Lyush/archive/2012/03/15/2398211.html

你可能感兴趣的文章
BZOJ1997:[HNOI2010]PLANAR——题解
查看>>
BZOJ1014:[JSOI2008]火星人prefix——题解
查看>>
使用Unity3D引擎开发赛车游戏
查看>>
HTML5新手入门指南
查看>>
opennebula 开发记录
查看>>
ubuntu 修改hostname
查看>>
sql 内联,左联,右联,全联
查看>>
C++关于字符串的处理
查看>>
6、Web Service-拦截器
查看>>
Flask 源码流程,上下文管理
查看>>
stream classdesc serialVersionUID = -7218828885279815404, local class serialVersionUID = 1.
查看>>
ZAB与Paxos算法的联系与区别
查看>>
java 读取本地的json文件
查看>>
Breaking parallel loops in .NET C# using the Stop method z
查看>>
Android Content Provider Guides
查看>>
修改故障转移群集心跳时间
查看>>
[轉]redis;mongodb;memcache三者的性能比較
查看>>
微软职位内部推荐-Sr DEV
查看>>
用计算器计算“异或CRC”
查看>>
让你的WPF程序在Win7下呈现Win8风格主题
查看>>