Jason237

题解

各类笔记(1)

/ 注册

全部文章 / 题解（共3篇）

题解|《算法竞赛进阶指南》没有上司的舞会

我又回来惹！这次发的还是dp（逃众所周知，dp分类极为广泛，最基础的有背包dp，线性dp，然后就是dp与各种算法的结合，例如与图论结合的DAG上的dp以及树性dp，与倍增结合的倍增dp，与位运算结合的状压dp...这次我要发惹就是树性dp的一道板子题“没有上司的舞会” 首先，我们来明确一下树形d...

图论《算法竞赛进阶指南》 dp

2019-08-31

3 920

题解|《算法竞赛进阶指南》Telephone Lines

题面描述：在某地有n座通信基站，p条双向电缆，第i条连接ai和bi。其中1号基站是总站，现有人希望通讯公司可以对电缆进行升级以期更好地使用，其中对第i条升级需要支付wi。而电缆公司正在搞活动，某人可以指定一条从1号基站到n号基站的路径，并指定路径上不超过k条电缆，通讯公司可免费进行升级，而收取的...

图论《算法竞赛进阶指南》

2019-08-21

1 769

题解|《算法竞赛进阶指南》数字组合

首先,这是一道典型的背包模板题(可以从比赛名称看出来(逃) 背包是线性dp中一类较为重要而又特殊的模型，大多都是有着固定的套路在里面.主要分为01背包,多重背包,完全背包，这三类的区别十分明显，01背包是单个物品只能取一次，多重背包是单个物品可以取有限次，而完全背包则可以取无限次，根据取的次数不同，...

《算法竞赛进阶指南》 dp

2019-08-16

4 796