夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色

标签:状压dp

2 篇文章

Luogu P1879 [USACO06NOV]Corn Fields G 题解
Describe 题目链接 给一个$M\times N$的矩阵,矩阵每个位置为$0/1$,问选一些$1$使这些不相邻的方案数。 Solution 明显状压$DP$。 那么怎么$DP$呢? 设$f[i][j]$表示第$i$行状态为$j$的方案数。 那么转移就可以暴力枚举上一行的状态再判断可能性转移。 $$f[i][j]+=f[i-1][k]$$ 那么…
Luogu P1896 [SCOI2005]互不侵犯 题解
Describe 题目链接 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 注:数据有加强(2018/4/25) 1 <=N <=9, 0 <= K <= N * N Solution 状压DP。 判断两个国王是否相互干扰…