首页 > 其他分享 >DP 套 DP(DP of DP)

DP 套 DP(DP of DP)

时间:2024-10-04 22:11:05浏览次数:4  
标签:le DP 内层 sim LIS dp

把 DP 过程当作状态进行 DP。DP of DP 一般数据范围不会太大,而且一般是计数题。

DP of DP 的本质是自动机上 DP。 大致上可以写作 \(dp[\dots][S]\) 表示外层 DP 进行到 \(\dots\) 阶段,内层 DP 对应到 \(S\) 阶段。

例一:基因

题意:给出串 \(s\) 和一个数 \(m\)。\(n=|s|\)。求对于 \(i=0\sim n\),有多少串 \(t\) 满足 \(|t|=m\) 且 \(LCS(s,t)=i\)。\(n\le 15,m\le 10^3\)。

假设我们已经知道这是一道 DP 套 DP 的题目。那么对于 DP套DP,最重要的想法就是考虑内层 DP 是怎么进行的

在这题,内层 DP 是 "最长公共子序列"。平时做 LCS,一般是 \(f[i][j]=\max(f[i-1][j],f[i][j-1],f[i-1][j-1]+[s_i=t_j])\)。

考虑完内层 DP,然后就要考虑怎么把内层 DP 的状态压缩入外层 DP 的状态。

因为 \(t\) 是变化的,所以 DP 时拿一维记录目前考虑到 \(t\) 的第 \(i\) 位了;对应的,考虑拿一维 \(S\) 记录此时 \(f[1\sim n][i]\) 的值。
DP of DP 中,一般数据量较小的那一边作为被压缩的内层 DP。 比如这题,\(n\le 15\),用 \(S\) 记录就只用压缩长度 \(15\) 的数组了。

但是我们面临第二个问题:怎么用 \(S\) 记录此时 \(f[1\sim n][i]\) 的值?总不可能开十五维数组。这个点也是大部分 DP of DP 的难点,怎么压缩内层 DP 的状态?这里需要一些神秘的观察。

观察:当 \(j\) 固定,\(f[x+1][j]-f[x][j]\in \{0,1\}\)。

证明:

按 \(j\) 的大小数学归纳法。\(j=1\) 显然。

若 \(f[x+1][j]=f[x][j]\),立即成立。

若 \(f[x+1][j]=f[x][j-1]+1\),又 \(f[x][j]\ge f[x][j-1]\),所以 \(f[x+1][j]-f[x][j]=f[x][j-1]+1-f[x][j]\le f[x][j-1]+1-f[x][j-1]=1\)。

若 \(f[x+1][j]=f[x+1][j-1]\),\(f[x][j]\ge f[x][j-1]\),由数学归纳法,\(f[x+1][j-1]-f[x][j-1]\le 1\),所以 \(f[x+1][j]-f[x][j]\le f[x+1][j-1]-f[x][j-1]\le 1\)。

证毕。

有了这个性质又怎么样?得出结论:\(\Delta f\) 是一个 \(01\) 序列,所以可以用一个二进制数 \(S\) 压缩这个差分数组。

因此可以定义出 \(dp[i][S]\):填 \(t\) 的前 \(i\) 位,\(\Delta f[1\sim n][i]\) 为 \(S\) 的方案数。最终 \(i\) 的答案就是 \(\sum dp[m][A]\),其中 \(A\) 是一个包含 \(i\) 个 \(1\) 的二进制数。

例二:BZOJ3591:最长上升子序列

题意:给出 \(1\sim n\) 的一个排列的某一个最长上升子序列(记其长度为 \(m\)),求原排列可能的种类数。\(n\le 15\)。

在这道题目里,内层 DP 就是 "最长上升子序列"。

经过瞪眼法,我们发现 \(f[i]\) 表示前 \(i\) 个数的 LIS 长度没有好的性质。难道要放弃了吗?

转念想到 LIS 的另一种求法:维护 \(f_i\) 表示长度 \(i\) 的 LIS 结尾数最小值。而这个数组就有比较好的性质了:它是单调递增的,而且每新加一个数进来,只会修改一个位置。每个数有三种状态:在 \(f\) 中,曾经在 \(f\) 中,还没考虑。用三进制压缩为 \(S\)。

\(dp[i][S]\) 表示填了前 \(i\) 位,此时 \(f\) 的状态为 \(S\) 的方案数。在转移时强制只能转移到合法的 \(S'\)。具体而言,假设这一步选择填 \(j\),必须满足:① 若 \(j\) 在给定的 LIS 内,要求 LIS 中 \(j\) 之前所有的数都填了;② 要求填了 \(j\) 后前 \(i+1\) 个数的 LIS 长度 \(\le m\)。

标签:le,DP,内层,sim,LIS,dp
From: https://www.cnblogs.com/FLY-lai/p/18446710

相关文章

  • 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++代码......
  • WordPress文章发布技巧:让你的内容脱颖而出
    在当今的数字时代,内容是吸引和保持网站访问者注意力的关键。WordPress作为一个强大的内容管理系统,提供了多种工具和功能来帮助你优化文章发布过程。以下是一些技巧,可以帮助你更有效地发布WordPress文章,确保你的内容脱颖而出。优化标题标题是文章的第一个印象,它需要吸引人且包......
  • 修改图片的DPI为300,图片格式转换成jpg,nodejs脚本
    //用sharp转换图片格式constSharp=require('sharp');//引入fs库用于文件操作constfs=require('fs');//引入path库用于处理文件路径constpath=require('path');//引入exiftool库用于处理图片元数据constexiftool=require('exiftool-vendored').exifto......
  • 一类特殊的区间 dp
    这东西去年就看了,但是感觉理解的不是很深刻。今年再来加深一下理解吧!虽然可能这辈子不会再用到了。先看一个题吧:CF1132F没什么分析的必要,直接给个转移方程吧。\[\begin{cases}f_{i,i}=1\\f_{l,r}=\min(f_{l+1,r},f_{l,r-1})&s_l=s_r\\f_{l,r}=\min\limits_{l\lek<r}f_{l,k}......
  • 1267:【例9.11】01背包问题(从二维优化一维dp问题)
    代码如下:#include<iostream>usingnamespacestd;intdp[10010],w[200],c[200];intmain(){ intm,n; cin>>m>>n; for(inti=1;i<=n;i++) { cin>>w[i]>>c[i]; } for(inti=1;i<=n;i++) { for(intj=m;j......
  • WordPress产品分类添加,自动排序插件
    效果图如下  目前这个预览菜单这个效果有点问题,但是不影响实际排序,有懂源码的朋友可以自行修改一下,目录结构menu-assetsmenu.cssmenu.jsmenu.php源码如下menu.php文件<?php/***PluginName:菜单整理*Description:将WooCommerce......