DP也练了一部分,找感觉。
说一下VIJOS上的。
◆线性连接性的问题(包括分配问题,转换问题,连接问题,及宏观扩展),这样的例子比较多,方程就是由一维来记录处理到的线性位置作为阶段,然后用额外的未来记录分配的情况,之前临近的连接情况等,这样一个一个把状态连接起来得最优
例子:
P1323化工厂装箱员 P1386矿工配餐 P1417魔法塔防 P1421更换轮胎 P1456最小总代价 P1470教主的后花园 P1002过河
◆线性的选择问题
这种就是类似最长不上升子序列之类的那种,当处理到i时,在前面选择一个可能的情况跟他连起来,例子比如说:
P1098合唱队形 P1331看球的巴士
◆开放的划分推进
这种一般就是一个二维的方程,表示把这一段分在一起,可以开额外的维来表示一些特殊的情况,这样可以已分段为阶段向后推进,这种一般可以用于一种按照某种规则划分,使划分的段数最优的问题,也就是划分的段数未知时,并且这个不适于环形的,记忆化的话会出问题。。。
例子:
P1306 递增序列 P1322解题
◆封闭的划分或者选择
一般就是二维的方程表示把这一段已经划分完毕后的情况,以划分的的长度为阶段,比较适合于给定划分段数的划分问题,可以处理环,用记忆化会比较好些。。。转移时可以枚举划分的中心或者这一部分中划分为独立的一段的位置
例子:
P1100加分二叉树 P1118统计单词个数 P1218数字游戏 P1312能量项链
◆树形DP
很好很强大的Dp,一般依托树上的关系进行转移,并且因为依托关系比较严重,所以会开几维来记录情况,将每种情况分开处理。一般,如果不愿意多叉转二叉,可以用哪种求和以后进行枚举儿子进行替换
例子
P1144小胖守皇宫 P1395HYH的逻辑电路
◆背包问题
背包是个很好很强大的东西,各种例子,应用太多了。。。包括分组背包,判定性背包,将诡异的东西作为物品什么的。。。例子:
P1025小飞侠游园方案 P1104采药 P1117数的划分 P1133装箱问题 P1198最佳课题选择 P1313今明的预算方案 P1317开心的今明 P1334NASA的食物计划 P1407古韵之刺绣
◆图上的DP
图上的DP一般都会有某种限制来形成阶段和无后效性,比如阶段图,方向限制,权值(编号)限制,时间线限制,找到这个阶段就好搞了,最好进行记忆化搜索
例子:P1011清帝疑惑之顺治 P1364吃吃吃 P1370采果子 P1474雷曼兔
◆多进程DP 多方向Dp
这些都是比较奇怪的类型,比如旅行商简化版,HILL,三取方格数。。。不具体说了
◆双位选择问题:
类似最长公共子序列那种的,有两种两种位置共同构成状态,然后根据限制条件,选择两边,或者放弃某一边
一些例子:
P1327回文词 P1378矩阵取数游戏
◆包含性的可行性DP
V囧上比较少,但是如果想不到最优性的DP,可以想这种可行性的。。。
◆◆注意的问题
多个小Dp组成,比如矩阵取数游戏,统计单词个数,合唱队形之类的,就是不同次的DP没有关系,但是总起来就解决问题了。
空间问题:考虑可不可以使用滚动数组,但那时滚动数组如果正推要考虑每次都进行初始化
数据范围:看清楚是否需要高精,另外如果用int64那么中间的变量也需要用int64
赋初始值:有时注意赋值为maxlongint时,注意是不是会不够大,中间过程会不会两个相加爆掉。。。
环形DP--处理环:处理环有好几种情况,比如依赖于划分的,主要问题就是划分点可能正好位于环的两端相连的的地方,所以一般的做法是拷贝环,然后枚举每个起始点,记忆化搜索,比如数字游戏,能量项链。另一种就是可能就是相邻的决策有限制条件,这样可以单独处理一下边界位置就行了,比如说1470后花园。
输出方案:状态转移的时候顺便记录,至于字典序的问题,不一定在每次DP的时候选择一个字典序比较靠前的,要想清楚,最好都记下来然后深搜或者用字符串排
相关推荐
DP83848-单路10100_Mbs以太网收发器在省电模式下的初始化
DP83848中文数据手册 DP83848中文文档 全篇翻译无排版 DP83848C / I / VYB / YB PHYTER™QFP单端口10/100 Mb...• 能量检测模式 • 25MHz时钟输出 筛选器 • IEEE 802.3 PCS,100BASE-TX收发器和滤波器 • IEEE 1149.1
绍了美国国家半导体公司的PHY芯片DP83848C的功能特性;给出了在RMII(Reduced Medium Independent Interface,精简的介质无关接口)模式下的硬件电路及软件设计,以及在PCB布局布线过程中的注意事项。该设计为嵌入式...
DP设计模式PPT_NEW_hao_123
DP83848的RMII模式硬件应用连接。
美国国家半导体产品DP83640的独特性能,即100 Mb/s 下的同步以太网技术,可在用以太网连接的IEEE1588精密时 间协议(PTP)系统之间实现非常精确的同步。采用这种特 性,便可工作在要求的网络拓扑约束内,实现PTP...
DP83848官方原理图示例 使用独立接口模式的网络模块。
科立讯最新研发推出的数字手持对讲机DP660符合标准DMR协议和ETSI TS 102 361-1, -2, 和-3的标准规范,支持Tier 1和Tier 2模式,兼容其他DMR终端,支持数字和模拟双模式,可实现模拟系统平滑过渡。 科立迅DP660/DP...
蓝牙A2DP 模式下,播放音乐频响&失真。TIA 920-B是一个全面的美国双带宽标准,适用于窄带(NB)和宽带(WB)设备。它还允许在自由场(FF)和漫反射场(DF)之间选择作为侦听器参考点(LRP)。这些序列测量具有符合...
Android 7.1 A2DP Sink patch20180117蓝牙音箱模式
直接测试模式 允许测试人员向 PHY 层发出指令以传输或接收给定数据包序列,通过 HCI 或 2 线 UART 接口提交命令。 主机控制器接口 (HCI) 蓝牙控制器子系统(底部三层)和蓝牙主机之间的可选标准接口。 逻辑链路...
Android 6.0 A2DP Sink patch20180117蓝牙音箱模式
ZWG-28DP具有三种数据传输模式,分别是GPRS方式、SMS方式和引脚控制(PIN)方式。当选择PIN方式时,用户的CPU通过控制ZWG-28DP的GPRS/SMS选择引脚(GPRS/SMS_CTR)的高低电平来选择传输方式。而且ZWG-28DP对GPRS和SMS...
DP模式:DP:0-1背包(0-1背包问题) 一劳永逸: : DP模式:无限背包 DP模式3:斐波那契数 盗贼: 强盗屋: : 众议院强盗2: ://leetcode.com/problems/house-robber-ii/discuss/59921/9-lines-0ms-O(1)-Space-...
OpenDDS的通讯分为几层,分别是发现层(Sdpd和Sedp)、传输层,可以通过日志输出直观的观察运行情况,加快对OpeDDS内部机制的了解
3229Android 5.0 A2DP Sink patch20180117蓝牙音箱模式
LT8619C HDMI1.4/双模式DP to 2Port LVDS/24Bit RGB+Audio,LT8619C是一款高性能HDMI1.4及双模DP接收器芯片,符合HDMI 1.4规范。TTL输出可支持RGB、BT656、BT1120,输出分辨率最高可支持4K×2K@30Hz。为了方便实现...
京瓷打印机ECOSYS M4028idn DP-4100维修手册
给出了在RMII(Reduced Medium Independent Interface,精简的介质无关接口)模式下的硬件电路及软件设计,以及在PCB布局布线过程中的注意事项。该设计为嵌入式系统中以太网底层的软硬件设计提供了参考,也为TCP/IP...