T1
题目
环形合并石子。
思路
把普通合并石子改成把石子的环复制一遍，然后从中间滑动一个长度为$n$的窗口，找出最小值即可。
T2
题目
折叠的定义如下：
- 一个字符串可以看成它自身的折叠。记作
S=S - $X(S)$是$X(X\geq 1)$个
S连接在一起的串的折叠。记作$X(S) = SSSS…S(X个S)$。 - 如果
A=A’,B=B’，则AB=A’B’例如，因为3(A)=AAA,2(B)=BB，所以3(A)C2(B)=AAACBB，而2(3(A)C)2(B)=AAACAAACBB
给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。
思路
$DP[i][j]表示s[i\sim j]$折叠后最小长度
$DP[i][j]=min(DP[i][k],DP[k+1][j]),O(n^3)$枚举$k$
$DP[i][j]=min(DP[i][i+t-1]$+复制次数的十进制位数+$2$)(整个区间折叠)（$t$是$s[i][j]$的整周期）
T3
题目
某一村庄在一条路线上安装了 $n$ 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为 $1m/s$，每个路灯的位置（是一个整数，即距路线起点的距离，单位：$m$）、功率（$W$），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
思路
$\displaystyle \sum_{i\geq 1}{\displaystyle \sum_{j}{W_j}}$
被关掉的灯是一个区间，经过灯一定会关掉。
$DP[i][j]$，[i~j]中的灯都被关掉的时候的最小功耗。
但是不知道此时人在哪里，所以$DP[i][j][k]$，k表示当前在k号灯。
跑的代价cost为使用时间*当前所有没有被关闭的灯的功率之和。这里每次从一个灯跑到旁边的一个灯，所以每次的$cost$其实就是没有关闭的灯的功率之和。
$DP[i][j][k]=min(DP[i-1][j][i-1]+(w_1+…+w_{i-1}+w_{j}+…+w_{n}))$
发现其实$[i~j]$的灯关闭后，人要么在$i$，要么在$j$。
所以转化为$DP[i][j][k] (k\in (0,1))$ $k$表示是在$i$还是$j$。
$DP[i][j][k]=min(DP[i+1][j][0]+cost_1,DP[i][j-1][1]+cost_2)$
T4
题目
给定长为$n$的序列$a[i]$，每次可以将连续一段回文序列消去，消去后左右两边会接到一起，求最少消几次能消完整个序列，$n≤500$。
思路
$DP[i][j]$ $[i\sim j]$删完min次
$DP[i][j]=min(DP[i][k]+DP[k+1][j])$
如果$s_i=s_j$，$DP[i][j]=min(DP[i][j],DP[i+1][j-1])$，（回文串前后加同样的字符还是回文串）
但是上一种情况下如果$i+1=j$，也就是说“被加上两头”的字符串是空的，那么就要+1，也就是$DP[i][j]=min(DP[i][j],DP[i+1][j-1])+1$。
T5
题目
来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。
外星人遵循已知的攻击模式。有 $N$ 个外星人进攻，第 $i$ 个进攻的外星人会在时间 $a_i$ 出现，距离你的距离为 $d_i$，它必须在时间 $b_i$ 前被消灭，否则被消灭的会是你。
你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 $R$，它会瞬间摧毁与你的距离在 $R$ 以内的所有外星人（可以等于），同时它也会消耗 $R$ 单位的燃料电池。
求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。
思路
以时间$T$为横轴，$d$为纵轴。
这样每一发大炮都可以被看做是一个柱子。这个柱子插下去之后，它穿过的所有区间都灰飞烟灭，没有穿过它的区间了，此后它两侧的区间没有任何联系。为了节省炮弹，肯定是发射到能穿过的区间里面的最高的一个区间，并且刚好发射到那里，因为他已经是最高的，再远也没有意义。设这个柱子的位置在$k$。它使用的燃料就是它分割的区间里面$d$最大的一个区间。
所以这个题的转移方程就是：
$DP[i][j]=min(DP[i][k]+DP[k+1][j]+maxD)（$$k$位于$d$最大的那个区间）
这个题时间的范围比较大，但是外星人数量较少，离散化即可。
T6
题目
已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值都比它左儿子结点的数据值大，而比它右儿子结点的数据值小。
另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的儿子结点的权值要小。
已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的、按照数据值排序的二叉查找树。
一个结点在树中的深度定义为它到树根的距离加 $1$。因此树的根结点的深度为 $1$。
每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为所有结点在树中的访问代价之和。
现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些结点的权值，但每次修改你会付出 $K$ 的额外修改代价。你可以把结点的权值改为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的问题是，整棵树的访问代价与额外修改代价的和最小是多少？
思路
首先找到整段中权值最小的点作为根，把他分成两部分。递归。
每个子树是一个区间。
$DP[i][j][t]$表示中序遍历$[i\sim j]$，且根的权值$\geq t$形成一个子树的代价 。
如果$a_k\geq t$：
- 可以进行修改：$DP[i][j][t]=min(DP[i][k-1][t]+DP[k+1][j][t]+K)$
- 可以不修改：$DP[i][j][t]=min(DP[i][k-1][t]+DP[k+1][j][t])+[i\sim j]$中访问频率之和
如果$a_k< t$：
$DP[i][j][t]=min(DP[i][k-1][t]+DP[k+1][j][t]+K+[i\sim j ]区间中访问频率之和)$
T7
题目
Consider an array $A$ of length $N$. You are planning to do several queries: for a segment $[i, j]$ of the array, find the maximum value on that segment of the array. The query for the indices $i$ and $j$ will be done $Q_{i, j}$ times.
But the array is not given, and you are going to build it right now.
For each $i$ from $1$ to $N$, you can select one of $K_i$ different values $V_{i, j}$ as the value of $A_i$, and the respective costs of choosing these values are $C_{i, j}$.
After all queries, your $score$ will be the sum of the results of all the interval queries you are planning to do, minus the cost of choosing the values $A_i$. Find the maximum possible score that can be achieved.
思路
$DP[i][j]$表示只考虑区间$[i\sim j]$中的询问，得到的$score-cost$的最大值。
$DP[i][j]=max(DP[i][k-1]+DP[k+1][j]+V*包含k的询问区间个数-C)$
$V_x-C$，相当于是求横坐标为$x$时，哪个一次函数值最大。
T8
题目
经过初步分析，这块海域可视为一个底边长为 $N$ 米，高为 $1001$ 米的长方形网格。其中网格的底边对应着她家的私人海滩，每一个 $1:\textrm{m}\times1:\textrm{m}$ 的小正方形都代表着一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之后，她要做的就是圈出她想要的游泳场啦。
她心目中理想的游泳场满足如下三个条件：
- 必须保证安全性。即游泳场中的每一个单位海域都是安全的。
- 必须是矩形。即游泳场必须是整个网格中的一个 $a\times b$ 的子网格。
- 必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。
例如：当 $N = 5$ 时，若测量的结果如下（因为 $1001$ 太大，这儿只画出网格最下面三行的信息，其他部分都是危险的）。
那么她可以选取最下面一行的 $1\times4$ 的子海域，也可以选择第三列的 $3\times1$ 的子海域。注意她不能选取最上面一行的 $1\times5$ 的子海域，因为它没有与海滩相邻。
为了让朋友们玩的开心，她想让游泳场的面积尽可能的大。因此她会选取最下面那一行的 $1\times4$ 的子海域作为最终方案。
虽然她要明天才能知道每一个单位海域是否安全，但是她现在就想行动起来估计一下她的游泳场面积有多大。经过简单的估计，她假设每一个单位海域都有独立的 $q$ 的概率是安全的，$1 − q$ 的概率是不安全的。她想要知道她能选择的最大的游泳场的面积恰好为 $K$ 的概率是多少。
然而久莲对数学并不感兴趣，因此她想让你来帮她计算一下这个数值。
思路
$DP[i][j][k]$表示$[i\sim j]$这段区间，最靠岸的危险区域$\geq k$ 并且最大的矩形区域$\leq k$的概率
$DP[i][j][k]=\displaystyle \sum_{距离为k，位置为t} {DP[i][l-1][t]DP[l+1][j][t-1]下面全都不是危险区域的概率}$
$DP[i][k]=\displaystyle \sum_{距离为k，位置为t}{DP[l-1][t]DP[i-l][t-1]*下面全都不是危险区域的概率(i(t-1)\leq K)}$
T9
题目
最大带权独立集。
思路
$DP[u][0/1]$为考虑$u$的整颗子树，$u$在/不在独立集内，得到的最大独立集。
$DP[u][0]=\displaystyle \sum_{v}{max(DP[v][1],DP[v][0])}$（下面选不选都可以）
$DP[u][0]=\displaystyle \sum_{v}{DP[v][0]}$（下面不可以选）
代码
1 | void dp(int x) { |
T10
题目
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？
思路
树上背包板子题。
$DP[u][i]$表示$u$子树中选了$i$个课程的最大学分。
$DP[u][i]=\displaystyle \max_{j_1,…,j_m且j_1+…+j_m}$
代码
1 | /************************************************************** |
T11
题目
2020 年，人类在火星上建立了一个庞大的基地群，总共有 $n$ 个基地。起初为了节约材料，人类只修建了 $n-1$ 条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地 $A$ 到基地 $B$ 至少要经过 $d$ 条道路的话，我们称基地A到基地B的距离为 $d$。
由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过 $2$ 的基地的火灾。
你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。
思路
状态设计
1 | F[i][0]表示可以覆盖到从节点i向上2层的最小消防站个数 |
状态转移
$F[i][0] = 1+\displaystyle\sum_{\text{s是i的儿子}} F[s][4]$
因为i可以覆盖到向上2层，所以它自己必须是消防站。此时，它可以覆盖到所有儿子和孙子，因此儿子的状态可以是F[s][0~4]中的任意一种情况。但因为我们需要使得消防站个数最少，所以取F[s][4]。
$F[i][1] = \displaystyle\min_{\text{s是i的儿子}}<!–swig6–> }\quad \text{和}F[i][0]\text{中的最小值}$
因为i可以覆盖到向上1层，所以存在两种情况：要么恰好覆盖到i上面的1层，要么向上覆盖2层。
如果恰好覆盖到向上1层，那么i的至少一个儿子必须是消防站。其它儿子的状态可以是F[t][0~3]中的任意一种。同样，因为要取消防站个数最小值，取F[t][3]。
而如果向上覆盖两层，情况和F[i][0]是一样的。
取这两者最小值。
$F[i][2] =\displaystyle \min_{\text{s是i的儿子}}<!–swig7–>}\quad \text{和}F[i][0\text{-}1]\text{中的最小值}$
因为i可以覆盖到向上0层，所以要么恰好向上覆盖0层，要么向上覆盖1~2层。
如果向上覆盖0层，那么i的至少一个孙子必须是消防站，其它儿子的状态可以是F[t][0~2]中的任意一种。取F[t][2]。
而如果向上覆盖两层，情况和F[i][0]和F[i][1]是一样的。
取这三者最小值。
$F[i][3] =\displaystyle \sum_{\text{s是i的儿子}}{F[s][2]}\quad \text{和}F[i][0\text{-}2]\text{中的最小值}$
如果i恰好可以覆盖到向上-1层，即所有儿子被覆盖就可以。于是取F[s][2]。其它情况和上面取最小值。
$F[i][4] =\displaystyle \sum_{\text{s是i的儿子}}{F[s][3]}\quad \text{和}F[i][0\text{-}3]\text{中的最小值}$
如果i恰好可以覆盖到向上-2层，即所有孙子被覆盖就可以。取F[s][3]。其它情况和上面取最小值。
于是……就这样啦。
最终目标
我们希望寻找当整棵树都被覆盖的时候的消防站最小值，于是需要覆盖到根的这一层，于是结果是F[1][2]。
T12
题目
有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0 \sim n$ 之内的正整数 $k$ ，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他 的 $n-k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。
思路
题目要求将k个点染成黑色，求黑点两两距离及白点两两距离，使他们之和最大。
我们可以将距离转化为路径，然后再将路径路径拆分成边，就可以记录每条边被经过的次数，直接计算即可。
很简单对吧？那么问题来了，距离转化为路径好理解，路径拆为边也好说，可是每条边被经过的次数怎么计算呢？
我们可以这样想，我们任意取两个同色的点，对于每一条边，若不在这两个点的路径上，我们自然不考虑，若是在两个点的路径上，那么这条边的计数加一。我们可以转换一下，若是两个点在边的一侧，则不影响计数，若在边的两侧，则边的计数加一。那么我们推广一下，便可以得出，一条边的两侧每有一对同色点，这条边就要被经过一次。也就是说，一条边被经过的次数等于边的两侧同色点个数的乘积。那么我们便可以求出每条边被经过的次数：
$tot=k(m-k)+(sz[v]-k)(n-m-sz[v]+k)$
$m$表示题目要求选的黑点数，$sz[v]$表示当前子节点的子树大小，$k$表示当前子节点的子树上已选择的黑点数
有了这个结论，我们就可以轻松地得出DP方程了。
$f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+tot*e[i].w)$
为什么$k$正序排列就是对的，倒序排列就是错的？
这道题$k$前几篇题解必须正序枚举的原因并不是什么要用$j-k$更新答案，而是因为正序枚举$k$是从$0$开始的，而这道题的状态转移必须要先将$k=0$的状态转移过来才能成立。也就是说，这只是个巧合，$j$的枚举要倒序没错，但$k$的枚举必须正序简直就是无稽之谈。要想避免这一情况，只需提前转移一下$k=0$的情况即可。
T13
题目
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：
1 | 2 5 |
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
思路
从叶节点向上翻，每一个点找出以它为根节点的1~q的最大利益，除叶节点外，因为父节点不可能只从一个子节点那里要q-1条边（连接父、子节点还有一条边），所以就用到了背包的思想。其实有种随机搭配的感觉，父节点的大儿子要m条边，小儿子要w条边，自己留q-m-w-1条用来连接根节点求最大。
val保存子、父边的苹果数，所以f[x][j-k-1]中，父节点自己留的可用边-1。
代码
1 | void dfs(int x){ |
T14
题目
小$Q$在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字$1,2,3…$.进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。
在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激烈电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。
激励电流在导线上的传播是需要花费时间的，对于每条边$e$，激励电流通过它需要的时间为$t_e$，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小$Q$有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？
思路
看输入数据，由于n个节点只有n-1条边，不难看出这是一棵树。我们可以反着思考，就是让所有叶子节点同时发出信号，然后这些信号同时到达根节点。于是我们可以自下而上的进行维护，使得每一节点所有子节点的信号同时到达该节点。
于是我们考虑如何维护。我们从根节点开始搜索，搜索到叶子节点，回溯的时候进行维护，先维护节点的所有子节点到该节点最大边权（边权为叶子节点到同时到达它所需要时间）。然后维护答案，答案为最大边权减去所有到子节点的边权。然后维护父节点的边权，父节点边权为该节点子节点的 最大边权+父节点到该节点的时间。然后就回溯，重复操作，到根节点为止。
代码
1 | void dfs(int x, int fa) |
