首页 > 其他分享 >状态压缩DP

状态压缩DP

时间:2022-11-13 23:34:29浏览次数:72  
标签:状态 判断 压缩 合法 && DP

一、状态压缩DP概述

1、概念
  • 状态压缩dp通过将状态转换成整数,来实现状态转移。
  • 前置知识:位运算(&、|、!、^)
  • 当要处理一些集合问题的时候,可以将状态转换为整数,运用二进制相关知识解决问题。

二、例题

1、互不侵犯
image

分析:

  • 前一行会决定后一行的选择
  • 状态转移方程:\(f[i][j][k] += f[i - 1][j - num[k]][k]\)
    f[i][j][k]表示前i行,放置j个国王,当前行选择合法状态k的方案数。
  • 每一行的合法状态判断:!(\(i\) & \(i\) >> 1)
    对于i的最高位来说,右移一位相当于把最高位的1移到次高位,如果此时相与结果为1,说明原来i的右边第一位是1,不是合法状态。
  • 行间合法状态判断:!(a & b) && !(a & b >> 1) && (a & b << 1)
    a & b:判断相邻行相同二进制位上是否相同
    a & b >> 1:判断某个位置右边是否为1

代码:


标签:状态,判断,压缩,合法,&&,DP
From: https://www.cnblogs.com/N-lim/p/16887697.html

相关文章

  • expdp导出sys用户下test表空间报错ora-31655
    数据库:oracle11.2.0.4系统:centos7.9问题描述:expdp导出sys用户下test表空间报错ora-31655,如下所示:[oracle@leo~]$expdp\'/assysdba\'directory=ts_expdpdumpfile=ts......
  • [期望DP]P1654 OSU!
    题目描述osu是一款群众喜闻乐见的休闲软件。我们可以把osu的规则简化与改编成以下的样子:一共有n次操作,每次操作只有成功与失败之分,成功对应1,失败对应0,n次操作对应为1......
  • TCP四次挥手会经历这么多状态
    TCP三次握手中讲述了序列号和建立连接,这一篇来说说释放连接。标志位TCP首部中在属性标志位,和建立连接、释放连接有关,位于保留和窗口字段中间,其中三个标识与断开连接有关......
  • (AtCoder Beginner Contest 277)E(分层图+最短路 or bfs搜两种状态)
    E-CrystalSwitches题目大意:给你n个点,m条边,连接成一个无向图,每个边最初有一个状态(0or1)表示是否能够通过,同时给k个开关位于k的顶点上,每次点击开关会使得所有路的状......
  • 组件之间的通信2-->vuex状态管理
    在上期,我们讲了父子组件的传递方式,但是,如果我们想知道这些数据从哪里来的话,就需要一层一层找父组件,最后才能找到数据,容易造成Prop逐级透传问题今天,我们将介绍另一......
  • 动态 dp 学习笔记
    好耶!来学新算法了(最近停课了就有时间学算法啦因为CSP-S考了个什么ddp然后我不会(CSP炸了)学了一个晚上加一个上午才学会(我太菜了)嗯嗯其实说起来是个很简单的东西.前......
  • 动态规划(Dynamic Programming)套路学习 ----- 动态规划、备忘录、dp table、状态压缩、
    明确套路:首先,动态规划问题的一般形式就是求最值。而求解动态规划的核心问题是穷举。动态规划三要素。重叠子问题最优子结构状态转移方程⭐ 实战:一、斐波那......
  • 基于QPSK+LDPC的微波信道误码率matlab仿真
    目录一、理论基础二、核心程序三、测试结果一、理论基础  1.1QPSKQPSK数字解调包括:模数转换、抽取或插值、匹配滤波、时钟和载波恢复等。在实际的调谐解调电......
  • 黑苹果 Big Sur 11.6 启动 HiDPI 功能
    黑苹果BigSur11.6启动HiDPI功能NUC10安装了BigSur11.6后,设置HiDPI功能 安装完黑苹果后,由于是1080P分辨率的屏幕,字体显示的非常小,看着很吃力。......
  • python检测网络连接状态的四种方法
    第一种importsocketipaddress=socket.gethostbyname(socket.gethostname())ifipaddress=='127.0.0.1':returnFalseelse:returnTrue缺......