首页 > 其他分享 >奇怪的DP

奇怪的DP

时间:2023-08-07 20:14:38浏览次数:40  
标签:10 树链 leq 区间 rm times 奇怪 DP

P5975 [CEOI2009] photo

很抽象的题

path

给定一个 \(n\times m\) 的矩形,从左下角 \((n,1)\) 出发,可以向右转或向前走,障碍物和走过的格子不能走,求走到 \((s,t)\) 的方案数,答案模 \(k\)

\(1\leq n,m\leq 40\),\(k\leq 10^9\)

只有方向不可做

设 \(f[a][b][x][y][0\cdots 3]\) 表示矩形 \((a,b,x,y)\) 从左上角、左下角、右上角、右下角进入的方案数。枚举走了多少步后再拐弯再进行转移

Paint Pearls

\(n\) 个位置,每个位置有 \(1\) 个目标颜色。每次选择一个区间,将区间所有的位置全部改成目标颜色。设区间内不同颜色的数量为 \(x\),则操作的代价为 \(x^2\),求最小代价

\(1\leq n\leq 5\times 10^4\)

设 \(f[i]\) 表示 \(1\) 到 \(i\) 的最小代价

下界是 \(n\)(一个个改)。因此若区间内不同颜色的数量超过 \(\sqrt{n}\),则不会直接操作。

记录当前位置往前 \(\sqrt{n}\) 种颜色及其对应位置即可

Data Structure You've Never Heard Of

给定一个长度为 \(n\) 的序列 \(a_1,a_2\dots a_n\),每个元素都是一个 \(d\) 维 \(01\) 向量,求所有不下降子序列的个数

\(1\leq n\leq 2\times 10^5\),\(1\leq d\leq 16\)

对于 \(d\) 维向量,\(a_i\leq a_j\) 等价于 \(a_i\) 的每一维都小于等于 \(a_i\)

\(a\leq b\) 等价于 \(a|b=b\),即 \(a\) 是 \(b\) 的子集,\(b\) 是 \(a\) 的超集

设 \(f[i]\) 表示以 \(i\) 为结尾的子序列的个数,时间复杂度 \(O(n^2)\)

考虑维护高位前缀和,设 \(s[a][b]\) 表示前 \(8\) 位是 \(a\),后 \(8\) 位是 \(b\) 的 \(f\) 之和

查询和修改的复杂度都是 \(O(n^{\frac{d}{2}})\)

Tree chain problem

一个 \(n\) 的点的树,\(m\) 条树链,第 \(i\) 条树链的价值为 \(w_i\)。请选择一些没有公共点的树链,使得价值和最大

\(1\leq n,m\leq 10^5\)

设 \(f[x]\) 为以 \(x\) 为根的子树内选取树链的价值最大值。枚举一条以 \(x\) 为 \(\rm LCA\) 的链 \((u,v,w)\),那么当前方案价值为 \(w\) 加上去除链上点后深度最小的点的 \(f\) 值

设 \(g[x]\) 为 \(x\) 的所有儿子的 \(f\) 之和

设链上的点为紫色,它们的儿子为绿色,那么绿色\(f\)之和 \(=\) 紫色\(g\)之和 \(-\) 紫色\(f\)之和 \(+\) \(\rm LCA\)特殊处理

问题转化为树上的树链查询与单点修改

建立 \(\rm dfs\) 序线段树 \(T\),\(t[x]\) 存储根到 \(x\) 的和

权值的单点修改转化成 \(\rm dfs\) 序上的区间修改

树链查询首先拆成两条链减去祖先

P3577 [POI2014] TUR-Tourism

困难

标签:10,树链,leq,区间,rm,times,奇怪,DP
From: https://www.cnblogs.com/xishanmeigao/p/17612595.html

相关文章

  • 状压 dp 变式
    利用\(dp_i\)的取值一开始这就是状压dp模版但是有时间要求,而且又要满足连续时间超过\(L\),显然连续时间越大越好那么\(dp_i\)的取值就是最大连续时间转移时可以根据\(dp_i\)进行二分,总时间复杂度能够勉强通过点击查看代码#include<algorithm>#include<iostrea......
  • Wordpress:如何修改Astra主题的(navigation)翻页模块?
    使用Astra搭建日文网站的时候,因为默认是英文,有些模块需要改成日文;比如分页器(navigation) 具体步骤如下:1.进入后台点击Appearance->Themefileeditor-> inc/core/class-theme-strings.php  2.将所有的需要修改的文本修改成日文; 3.修改成功后,提示Fileeditedsuc......
  • uniapp获取位置时显示getLocation:fail the api need to be declared in the required
    uniapp获取位置时显示getLocation:failtheapineedtobedeclaredintherequiredPrivateInfosfieldinapp.json/ext.json解决方式:1.manifest.json文件 "mp-weixin" 中添加"permission":{"scope.userLocation":{&quo......
  • Atcoder Grand Contest 058 F - Authentic Tree DP
    考虑给\(f(T)\)赋予组合意义。一个直观的想法是,在每条边中间新建一个节点,然后每次选择一条边对应的点,然后把它删掉,递归剩余的两个部分,但是你会发现这样分母不对,应该是\(n\)但在这个模型里只有\(n-1\)。考虑魔改这个模型。我们在每个边对应的点下面添加\(998244352\)个点,你......
  • 一些DP
    P1273有线电视网树上背包的变形\[f_{u,j+k}=\max_{v\inson(u)}f_{u,j}+f_{v,k}-w_{u,v}\]这里写成\(j+k\)是为了和代码一致。\(f_{u,j+k}\) 代表以\(u\)为根的子树中,选择了\(j+k\)个叶子结点的利润最大值。\(w_{u,v}\)代表\(u\)到\(v\)的......
  • m基于QPSK+LDPC的载波同步和定时同步matlab性能仿真,包括Costas和gardner环,LDPC,四倍
    1.算法仿真效果matlab2022a仿真结果如下:本程序在博主之前的《基于QPSK的载波同步和定时同步性能仿真,包括Costas环的gardner环》算法基础上,加入了LDPC编译码进行仿真。2.算法涉及理论知识概要载波同步是相干解调的基础,不管对于模拟通信还是数字通信来说,只要是相干解调,接收端......
  • m基于QPSK+LDPC的载波同步和定时同步matlab性能仿真,包括Costas和gardner环,LDPC,四倍
    1.算法仿真效果matlab2022a仿真结果如下:   本程序在博主之前的 《基于QPSK的载波同步和定时同步性能仿真,包括Costas环的gardner环》 算法基础上,加入了LDPC编译码进行仿真。 2.算法涉及理论知识概要       载波同步是相干解调的基础,不管对于模拟通信还......
  • 星融元:DPU替代网络可视化专用设备实现业务报文深度处理
    网络可视化中的深度业务处理网络可视化场景中,通常需要将采集过来的数据经过深度业务处理后再交给后端分析系统。这些深度业务处理功能包括:传统的深度业务处理通常由带CPU的框式设备完成,但框式设备成本高、功耗大、扩展不够灵活的种种给客户带来了极大的困扰。DPU算力的池化应用Heli......
  • udp发送上位机(1)
    发送彩色视频RGB888时,在上位机,通过BGR2BGR565转换为16位数据,再传输时加上行号,在DMA里也要对读出的数据进行高低位的变换,组成RGB565格式如下图所示,在灰度图时将每帧刷新改为了每一行刷新,这是因为在彩色图像时,刷新一帧的时间大于2ms,而灰度时为0.7ms,这就会导致在刷新的时候,新的数据......
  • SOS DP(子集 DP)
    Part1:前置知识1、状压DP2、基本的位运算操作Part2:SOSDP(以下的内容大部分翻译至CF上的原文)1、例题引入给定一个含\(2^N\)个整数的集合\(A\),我们需要计算:\(\forallx\subseteqA\),\(x\)中所有元素\(i\)的\(A[i]\)的和,即求:\[F[mask]=\sum\limits_{i\subseteq......