每日闲话

• 去还没干的篮球场，打篮球，鞋子全湿了，还bzd是否喝到了一些“篮球场水”...

今天看到了几句很好的话：

• dp 的优化基本就是对着原来的代码做等价变形。

• 对于这种区间覆盖问题大部分情况是贪心，小部分情况是DP，还有极少部分是网络流

练题

Hot Start Up

CF1799D1 (easy version)

CF1799D2 (hard version)

思路

对于我来说非常难想啊。

一、首先看 $n,k\le 5000$ 时，这边很容易想到定义 $f_{k,i,j}$ 为运行完前 $k$ 个程序时，第 $1$ 个 CPU 最后的程序类型是 $i$，第 $2$ 个 CPU 最后的程序类型是 $j$ 时的最短时间，然后就可以推出：

$\{\begin{array}{l}{f}_{k-1,i,j}+col{d}_{a_k}\to f_{k,a_k,j}\\ f_{k-1,i,j}+col{d}_{a_k}\to f_{k,i,a_k}\\ f_{k-1,i,a_k}+ho{t}_{a_k}\to f_{k,i,a_k}\\ f_{k-1,a_k,j}+ho{t}_{a_k}\to f_{k,a_k,j}\end{array}$

时间复杂度为 $O(n{k}^2)$。

接着就玄妙了，可以想到两个 CPU 中肯定有一个是 $a_{k-1}$，那么就可以优化掉一维，$f_{k,i}$ 为运行完前 $k$ 个程序时，第 $1$ 个 CPU 最后的程序类型是 $i$，同样也可以推出第 $2$ 个 CPU 最后的程序类型。再通过小小贪心，进行转移即可，时间复杂度为 $O(nk)$，细见代码。

然后，让我们进发这个问题的“硬版本”，$n,k\le 3\times {10}^5$，可以发现原来的转移方程似乎可以用线段树优化哎，只需要无脑区间修改和区间求最小值操作即可。

---

Too Many Segments

CF1249D1 (easy version)

CF1249D2 (hard version)

思路

这题就直入正解，跟闲话中的一样，这题考虑贪心，并用优先队列（堆）去维护，对于当前点 $i$ 被覆盖的次数，可以用前缀和 $su{m}_i$ 维护，若 $su{m}_i>k$，那么要删掉 $su{m}_i-k$ 条线段，可以证得所删掉的线段右端点 $r$ 越远越优，暴力求即可。

拓展

关于优先队列的排序：

struct Node {
	int l,r;
	int id;
} a[N];
struct cmp {
	inline int operator () (const Node& x, const Node& y) const {
		return x.r<y.r;
	}
};
priority_queue<Node,vector<Node>,cmp> q;

这里由于 priority_queue 全部和 sort 等是相反的，且默认是大根堆。

这代码里的 cmp 里虽然定义是 $<$，可反过来就是 $>$ 了 （口胡解释）。详细见文章，其中有讲。

非常nice的文章：

一文讲明白优先级队列为啥按less排序却是从大到小