首先，今天写一道大水题，因为是水题，就想浪一些，正好旁边一位大佬正在用map解紫题，于是就qaq.... 自己先上网搜了一下，发现结果不尽如人意，大多是一些教科书类的呆板解释，身为蒟蒻的我自然是看不懂...所以就问了一下大佬 首先，使用map时需要其专属头文件#include <map> 当然，你可以用万能头代替#include <bits/stdc++.h> 其次是定义变量，基本格式为map <变量类型1，变量类型2> 变量名ex.map <string,int> m(接下来均用次格式演示) map的添加数据：m[变量类型1] = 变量类型2...

我又回来惹！ 这次发的还是dp（逃 众所周知，dp分类极为广泛，最基础的有背包dp，线性dp，然后就是dp与各种算法的结合，例如与图论结合的DAG上的dp以及树性dp，与倍增结合的倍增dp，与位运算结合的状压dp...这次我要发惹就是树性dp的一道板子题“没有上司的舞会” 首先，我们来明确一下树形dp的定义。树形dp分为树形以及dp两方面，简单来说即为在树上跑dp，dp最重要的几大性质之一就是dp一般都可以分为若干个阶段，而在树形图上设计dp就较为简单，我们一般都以节点从深到浅（子树从小到大）的顺序作为dp的‘阶段’，又由于树形dp由深入浅的性质，我们一般用深搜来完成dp的状态转移。 以上就是...

题面描述： 在某地有n座通信基站，p条双向电缆，第i条连接ai和bi。其中1号基站是总站，现有人希望通讯公司可以对电缆进行升级以期更好地使用，其中对第i条升级需要支付wi。 而电缆公司正在搞活动，某人可以指定一条从1号基站到n号基站的路径，并指定路径上不超过k条电缆，通讯公司可免费进行升级，而收取的费用也仅仅为升级该路径上剩下电缆中最贵的所需花费即可。 问至少要多少钱能完成升级？ 简单来说，就是求一条从1到n的最短路，使得路径上第k+1大的边权最小 思路： 我们可以通过二分查找出第k+1条边的边权，边界值l为0，r为1000000.至于内部如何处理，我们可以将边权小于mid的边的边权看做为0...

首先,这是一道典型的背包模板题(可以从比赛名称看出来(逃) 背包是线性dp中一类较为重要而又特殊的模型，大多都是有着固定的套路在里面.主要分为01背包,多重背包,完全背包，这三类的区别十分明显，01背包是单个物品只能取一次，多重背包是单个物品可以取有限次，而完全背包则可以取无限次，根据取的次数不同，三种背包的核心代码也会稍有不同.除此之外就是这三类的各种混搭变形与优化，难度都不是特别大，只要可以保证足够的刷题量就可以将这个模块吃下.所以对于还不熟悉这个套路的人,蒟蒻在这里列出来一个题单(仅供参考 简单题&经典题 luogu P1048 采药 luogu P1060 开心的金明 luo...