首页 > 编程语言 >【算法】状态压缩DP

【算法】状态压缩DP

时间:2024-11-09 22:30:18浏览次数:3  
标签:状态 种植 压缩 玉米田 range states 相邻 算法 DP

基本内容

题目简述:在一个\(N\times M\)的玉米田中种玉米,有一些坏掉的土地是不能种玉米的,另外相邻的两个田也不可以种,一共有多少种种植方案(荒地也算一种),如图所示,由于相邻的土地不能种植,此时一号土地已经不能种植

image

  • 暴力解法

​ 每一行的玉米田有\(2^M\)种种植状态,再加上每一行的状态搜索,共有\(2^{M+N}\)种状态,并且还需要判断该状态是否合法,时间复杂度非常高。

  • 只考虑一行玉米田状态

​ 由于每一行的状态都是\(2^M\)种,并且可以种植的满足条件一致: ① 坏田不能种植 ② 相邻的田不能种植

​ 首先只考虑相邻田不能种植的情况 ① 坏田不能种植 ,可以发现,若只考虑玉米田只有一行的情况下,每一行的满足状态都是一样的,因此,可以先对不满足的种植状态去除。当我们用 0,1 表示田地的种植状态时,M列的玉米田可表示一个M位二进制数。例如该状态可以表示为二进制数 101,即为5,通过一个十进制数来表示当前行玉米田的状态。在遍历状态时可以减少运算效率。

image

def check(x):
    for i in range(m): 
        if (x >> i & 1) & (x >> (i + 1) & 1): #(位运算,若为1则表示有相邻的玉米田种植,不满足状态)
            return False
    return True
  • 考虑多行玉米田状态

​ 由于受到相邻田不能种植的条件影响,当第\(i-1\)行\(M\)列的玉米田被种植时,第\(i\)行\(M\)列就无法被种植,可以发现每一行的状态只受到上一行状态的影响,并且当\(i-1\)行的状态确定时,第\(i\)行的状态数目也确定了,这也就是状态压缩DP的关键,将多行的状态变换用一个状态转移的方式表示出来。如图所示,左图第一行的种植状态是100,第二行可以满足的数目是3;由于右图第二行的种植状态与其一致,因此右图第三行的满足数目也是3,

image

​ 将第\(i-1\)行的状态设为\(a\),第\(i\)的状态设为\(b\),满足状态的代码如下所示:

# states 存储的是玉米田只有一行时的满足状态
# heads 一个字典,存储某一个状态可以转化为下一行的全部状态
for i in range(len(states)):
    for j in range(len(states)):
        a, b = states[i], states[j]
        if (a & b) == 0: # 表示上下没有相邻的1,若有,则会出现某一位二进制位为1,不为0
            heads[a].append(b) # 将b的状态加入到a的满足状态中
  • 坏田不能种植

​ 当分析完相邻的田不能种植条件后,还需要分析坏田不能种植的情况,相对于上面的状态转移,这种情况较好分析,只需要满足当前行玉米田的坏田状态与当前状态是否有同时为1的列即可,若有则当前状态不满足,若无则满足,该条件判断与判断相邻行是否同时种植一致

  • 解题代码
M, N = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(M)]
g = [(~int("".join(map(str, row)), 2)) & ((1 << N) - 1) for row in data]  # 取反
mod = 100000000 
g.append(1 << N)

def check(x):
    for i in range(N): 
        if (x >> i & 1) & (x >> (i + 1) & 1):  # 位运算,若有相邻的玉米田种植,不满足状态
            return False
    return True
heads = {}
states = []
for i in range(1 << N):
    if check(i):
        states.append(i)
        heads[i] = []

for i in range(len(states)):
    for j in range(len(states)):
        a, b = states[i], states[j]
        if (a & b) == 0: # 表示上下没有相邻的1,若有,则会出现某一位二进制位为1,不为0
            heads[a].append(b) # 将b的状态加入到a的满足状态中
f = [[0 for _ in range(1 << N)]for _ in range(M + 2)]
f[0][0] = 1
for i in range(1, M+2): #本来是遍历到M即可,但遍历到M+1时可以在最后输出的时候直接取0状态即为前M层的最大数量
    for a in states:
        if g[i-1] & a:
            continue
        for b in heads[a]:
            f[i][a] = (f[i][a] + f[i-1][b]) % mod
print(f[M+1][0]) 

题目

  1. N皇后问题

题目与玉米田的思路基本一致,多了一个判断问题,即对角的国王也会相互攻击,为了加入此情况,在状态转移的判断条件上需要加入对角判断的处理

image

  • 状态满足代码修改
for i in range(len(states)):
    for j in range(len(states)):
        a, b = states[i], states[j]
        if (a & b) == 0 and check(a | b):# 只需在这部分上加入check(a | b),因为对角没有互相攻击即为交集没有相邻的两个皇后
            heads[a].append(b) 

标签:状态,种植,压缩,玉米田,range,states,相邻,算法,DP
From: https://www.cnblogs.com/DLShark/p/18537418

相关文章

  • 关于 DP 的非常规优化
    感觉这个东西就是玄学啊,考场上真的有人能想得出来嘛。(还是我太菜了qwq)思想现在见到的有这几种:从\(i\)推到\(i+1\)时状态改变的数量不会太多,直接继承可以优化。可能对答案有贡献的状态不会太多。即通过一些性质来消除掉冗余状态以保证时间复杂度。ABC176FBraveCH......
  • 【VBA实战】用Excel制作排序算法动画续
    为什么会产生用excel来制作排序算法动画的念头,参见【VBA实战】用Excel制作排序算法动画一文。这篇文章贴出我所制作的所有排序算法动画效果和源码,供大家参考。冒泡排序:插入排序:选择排序:快速排序:归并排序:堆排序:希尔排序:完整源码如下。OptionExplicitPublichm......
  • 知识点:算法策略
    知识点:在软考中,常考的算法策略包括分治法、动态规划法、贪心法、回溯法等。下面详细介绍这些算法策略的原理、适用场景以及算法复杂度:1.分治法原理:分治法是将一个复杂的问题分解成若干个相同或相似的子问题,递归解决子问题,然后将子问题的解合并以解决原问题。适用场景:适用于可......
  • Windows 11 对于 BZip2、Gzip、XZ 和 Zstandard 这些压缩格式的支持情况如下表所示:Win
      BZip2、Gzip、XZ和Zstandard(Zstd)是四种常见的压缩算法,它们在不同的应用场景中有各自的优势。下面是它们的详细说明:1. BZip2 (Block-sortingcompressionalgorithm)格式扩展名:.bz2压缩算法原理:BZip2使用Burrows-WheelerTransform(BWT)和Move-to-Front......
  • InDepth Guide to Denoising Diffusion Probabilistic Models DDPM:DDPM扩散概率模型去
    AnIn-DepthGuidetoDenoisingDiffusionProbabilisticModelsDDPM–TheorytoImplementation中文翻译:DDPM扩散概率模型去噪深度指南——理论到实现https://learnopencv.com/denoising-diffusion-probabilistic-models/#forward-diffusion-equationhttps://github.com/......
  • 代码随想录算法训练营day41| 188.买卖股票的最佳时机IV 309.最佳买卖股票时机含冷冻
    学习资料:https://programmercarl.com/0188.买卖股票的最佳时机IV.html#算法公开课动态规划之股票系列(2)主要是要分持股状态来讨论各种情况,并由前一天的情况来讨论今天的金额学习记录:188.买卖股票的最佳时机IV(相当于2k+1维度)点击查看代码classSolution:defmaxProfit(s......
  • 排序算法 - 冒泡
    文章目录1.冒泡排序1.1简介1.2基本步骤:1.3示例代码(C)1.4复杂度分析1.5动画展示1.冒泡排序1.1简介冒泡排序(BubbleSort)是一种简单的排序算法,其基本思想是通过相邻元素的比较和交换,把最大的元素逐步“冒泡”到列表的末尾。该算法的名称来源于较小的元素会逐......
  • 计算机网络 - UDP 协议
    定义UDP(UserDatagramProtocol)用户数据报协议:是一种无连接的数据传输协议,传输前不需要建立连接,没有复杂的协议优点是:首部开销小,不需要连接,机制简单,可以一对一,一对多,多对一通信,使用与直播、视频通话等业务领域缺点是:传输无序,不能保证消息一定送到,有丢包的问题报文如下UDP报......
  • 数值分析作业(第五章):代码+手写计算:插值算法 - Lagrange插值、Newton插值、Hermite插值
    《数值计算方法》丁丽娟-数值实验作业-第五章(MATLAB)作业P171:1,3,6,7,8,15,16数值实验P175:1代码+手写计算:插值算法-Lagrange插值、Newton插值、Hermite插值、分段插值推荐网课:数值分析-东南大学-bilibili数值实验作业(第五章)代码仓库:https://github.com/sylvandi......
  • 算法求解(C#)-- 寻找包含目标字符串的最短子串算法
    1.引言在字符串处理中,我们经常需要从一个较长的字符串中找到包含特定目标字符串的最短子串。这个问题在文本搜索、基因序列分析等领域有着广泛的应用。本文将介绍一种高效的算法来解决这个问题。2.问题描述给定一个源字符串source和一个目标字符串target,我们需要找......