中高等DP总结（更新中

1.CF613D Kingdom and its Cities

题意：给定一棵树，每个询问给出一些关键点，要求删掉最少的点使这些点两两不联通，无解输出-1。

思路：先判无解：只要有一个关键点的父亲也是关键点就无解。因为会被删除的点肯定是这些点中一些点的\(lca\)，所以考虑建虚树，然后树形DP。具体来讲，设\(g_x\)表示当前有没有关键点与\(x\)直接联通（若\(x\)为关键点则\(g_x=1\)），\(f_x\)表示点\(x\)的答案。转移时先\(f_x=\sum\limits_{y\in son(x)}f_y\)，然后根据\(x\)是否是关键点与\(\sum\limits_{y\in son(x)}g_y\)的值（设为\(sum\)）分类讨论：

1.\(g_x=0\)：
如果\(sum>1\)那就将点\(x\)删去，\(f_x++\)；
如果\(sum=1\)那就将\(g_x=1\)
如果\(sum=0\)自然不变

2.\(g_x=1\)那与\(x\)联通的点都得删，\(f_x+=sum\)

最后\(f_1\)就是答案，复杂度\(\sum n\times\log(\sum n)\)

2.P2519 [HAOI2011]problem a

题意：一次考试共有\(n\)个人参加，可能出现多个人成绩相同的情况。第\(i\)个人说：“有\(a_i\)个人成绩比我高,\(b_i\)个人成绩比我低。”请求出最少有几个人没有说真话。(其实这就是原题面，这么简洁那我不直接复制过来)

思路：（十分人类智慧，不知道是怎么想出来的）首先定义一个人的排名是严格高于他的人数加1，然后就可以把每个限制改成：“我是第\(a_i+1\)名，算上自己共有\(n-a_i-b_i\)个人与我同分”，然后变成区间\([a_i+1,n-b_i]\)表示与第\(i\)个人分数相同的区间，并把这个区间的权值定义为区间长度与所有\(a_j=a_i+1，j=n-b_i\)的\(j\)的个数的较小值。然后我们就把问题转化成了要选出若干不交的区间，最大化权值和。

我们发现，对\(f_i\)做贡献的\(j\)要满足\(r_j<l_i\),因此将所有区间按\(r\)排序后\(j\)就是一个前缀的形式，转移时二分出最大的\(j\)，再维护一个前缀最大值即可完成转移。复杂度\(nlog(n)\)

3.P6047 丝之割

题意：有若干条形如\((u,v)\)的弦，可以进行若干次操作，每次操作选定\((i,j)\)，会切断所有满足\(u>i,j<v\)的弦会被破坏，代价为\(a_i\times b_j\)，求破坏所有弦的最小代价。

思路：斜优裸题（只可惜第一步没想出来）先考虑那些弦不会做贡献，很容易发现如果有两个弦\(i,j\)满足\(u_j>u_i,v_j<v_i\)那么如果要删弦\(i\)就一定会同时删弦\(j\)，那么弦\(j\)就不做贡献。当我们把所有不做贡献的弦\(j\)删去后，就不会存在一条弦的\(u\)大于另一条弦的\(u\)而\(v\)较小，换而言之就是弦的\(u,v\)都是单增的有了这个性质就很好DP了。

设\(f_i\)为破环前\(i\)个弦的最小代价，转移方程为\(f_i=\sum\limits_{j=1}^{i-1}f_j+min(\)