首页 > 其他分享 >DP套DP

DP套DP

时间:2024-10-07 08:50:25浏览次数:5  
标签:le vert min text 复杂度 DP

该技巧通常用来求满足某个要求的元素数量,而对于要求的判定需要 DP 解决。

因此我们将判定 DP 的结果作为计数 DP 的状态来进行计数。

P4590 [TJOI2018] 游园会

题意:给你一个字符串 \(s\),求满足条件的字符串 \(t\) 的数量:\(\vert t\vert = n,\ \text{lcs}(s, t) = i,\ \text{"NOI"} \notin t\)。

对每个 \(i \in [0, \vert s\vert]\) 求出答案。\(\vert s\vert \le 15,\ n \le 10^3,\ \sum = \{\text{N},\text{O}, \text{I}\}\)。

设 \(f_{i, j}\) 表示 \(t\) 的前缀 \(i\) 和 \(s\) 的前缀 \(t\) 的 lcs(最长公共子序列):

\[f_{i, j} = \begin{cases} f_{i - 1, j - 1} + 1 & t_i = s_j\\ \\ \max(f_{i - 1, j},\ f_{i, j - 1}) & t_i \ne s_j \end{cases} \]

要想得到 \(f_i\),我们只需知道 \(f_{i - 1}\) 和 \(t_i\),且每种方案唯一对应一组 \(f_{i - 1}, t_i\)。

把 \(f_{i}\) 压入状态减小复杂度。\(dp(i, f_i)\) 表示考虑了前 \(i\) 个字符,第 \(i\) 维 dp 数组为 \(f_i\) 的方案数,枚举 \(t_i\) 转移

合法的 \(f_{i}\) 实际很少,注意到 \(0\le f_{i, j} - f_{i, j - 1} \le 1\),每一种合法方案差分后能唯一对应一个长度为 \(\vert s\vert\) 的二进制数。

对于子串的限制,再记录一维 \(k\) 表示匹配到 "NOI" 的哪一位即可。

预处理每种 \(f_{i - 1}\) 以及 \(t_i\) 会转移到哪个 \(f_i\),时间复杂度 \(O(2^{\vert s\vert} n)\)。submission

CF578D LCS Again

题意:给定字符串 \(s\),求满足 \(\text{lcs}(s, t) = n - 1\) 的字符串数量。\(n \le 10^5\)。

继续延续上题做法不是很牛,复杂度高达 \(2^nn\)。

考虑哪些状态是一定无用的。\(\text{lcs}(i, j) \le \min(i, j)\),后缀 \(i, j\) 能匹配的最大长度是 \(\min(n - i, n - j)\)。

必须满足 \(\min(i, j) + \min(n - i, n - j) = n - \vert i - j\vert \ge n - 1\) 才可能对答案产生贡献。

需要考虑的状态一共就三个:\(f_{i, i - 1},\ f_{i, i},\ f_{i, i + 1}\)。

再注意到 \(f_{i, j} \ge \min(i, j) - 1\),否则也不能产生贡献。

设 \(dp_{i, 0/1, 0/1, 0/1}\) 表示 三项分别为 \(\{i - 2, i - 1\},\ \{i - 1, i\},\ \{i - 1, i\}\) 的方案数,复杂度 \(O(\vert \sum\vert n)\)。

submission

标签:le,vert,min,text,复杂度,DP
From: https://www.cnblogs.com/Luxinze/p/18449743

相关文章

  • E61 树形DP P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟
    视频链接:  P8744[蓝桥杯2021省A]左孩子右兄弟-洛谷|计算机科学教育新生态(luogu.com.cn)//树形DPO(n)#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intn,f[N],son[N];inthead[N],idx;structE{intv,ne;}e[N<<1];voidadd(intu......
  • 树上深度和问题 - 换根DP
    问题引出:给出\(n\)个点的树,求出分别以不同的\(i\)为根时,所有结点深度的和,根节点的深度为\(0\)。首先我们有个自然的暴力思路,也就是以每个节点为根节点做一遍\(dfs\)这样的复杂度是\(O(n^2)\)级别的,所以要进行优化看下图:我们首先假设每个节点具有点权,明显这......
  • NOIP 前 dp 做题小记
    NOIP前dp做题小记[BJOI2019]排兵布阵设\(f(i,j)\)表示在前\(i\)个城堡中总共派遣\(j\)个士兵时,可以获得的最大分数。初始化:\(\forall0\lej\lem\),\(f(0,j)=0\)答案统计:\(ans=f(n,m)\)转移:\(f(i,j)=\max_{0\lek\lej}f(i-1,j-k)+g(i,k)......
  • 斜率优化 DP
    斜率优化DP在单调队列优化过程中,转移方程被拆成了两部分,第一部分仅与\(j\)有关,而另一部分仅与\(i\)有关,因此我们可以利用单调队列仅维护与\(j\)有关的部分,实现问题的快速求解。但仍然有很多转移方程,\(i\)和\(j\)是紧密相关的,这个时候单调队列优化就不适用了,例如如下转......
  • DP 套 DP(DP of DP)
    把DP过程当作状态进行DP。DPofDP一般数据范围不会太大,而且一般是计数题。DPofDP的本质是自动机上DP。大致上可以写作\(dp[\dots][S]\)表示外层DP进行到\(\dots\)阶段,内层DP对应到\(S\)阶段。例一:基因题意:给出串\(s\)和一个数\(m\)。\(n=|s|\)。求对于......
  • TCPUDP 共用端口问题
    TCP/UDP共用端口问题。转载自:TCP/UDP占用端口问题总结-mengban-博客园(cnblogs.com)1.TCPUDP可以共同占用一个端口号吗?首先明确一点端口是一种抽象的软件结构(包括一些数据结构和I/O缓冲区)。应用程序(即进程)通过系统调用与某端口建立连接(binding)后,传输层传给该端口......
  • 基于DPAPI+RDP技术实现本地打开远程程序,并映射到本地机器桌面上
    本教程使用工具所使用的环境说明:启动器开发工具:VS2022启动器所用客户端技术:.NET8+WPF启动器其他技术:DPAPI启动器发布的可执行程序,系统要求:Windows7以及以上,X64如果需要本程序,可以在网盘获取。网盘地址:链接:https://pan.baidu.com/s/1QPstE5-1zPK-qOp8GQ90ew?pwd=6666......
  • CodeForces - 118D - dp
    这道题的思路可能来源于步兵后面必须跟骑兵,反之亦然,那么一个兵种当前的状态肯定是由另一个兵种上一个的状态推来的(即取用该当前取用的兵种之前)。接下来就要考虑怎么控制每次取用多少个人了,由题意可知,每次取用不得超过k1或k2,我们从1-n1和从1-n2表示骑兵和步兵当前的数量表示......
  • 单调队列优化 DP
    单调队列可以\(O(n)\)求出子区间的最值,且顺序上要求区间的左端点和右端点单调不降。引入P1886滑动窗口/【模板】单调队列定义一个队列\(q\),我们让\(q\)中的元素满足单调不降。因此当\(x\)入队时,从前往后让不在当前范围的元素出队,从后往前将\(<x\)的元素全部出队,然......
  • 每日OJ题_牛客_DP2跳台阶_动态规划_C++_Java
    目录牛客_DP2跳台阶_动态规划题目解析C++代码Java代码牛客_DP2跳台阶_动态规划跳台阶_牛客题霸_牛客网题目解析        当前值只和数组的前两个值有关,在往前面的就无关了,所以没必要申请一个数组,直接使用两个变量即可,这样空间复杂度就满足要求了。C++代码......