给定一个DAG，定义链：一条链内任意两点之间都存在一条路径反链：任意两点都不存在路径Dilworth定理：最长反链\(=\)最小链覆盖。最小链覆盖内一个点只能归属于一条链，但链不一定是连续的。事实上这个还能转化为“选出若干条（一般定义下的）链，但一个点可以在多条链内”，本质相同。

期望得分：100+0+30=130实际得分：100+20+30=150T1感觉没有大样例也还是可以猜到那么一点的结论。k=0无解。当k≠0时，考虑交换不含1的两项，一定能使这两个位置都符合gcd(i,ai)=1，如果最后长度为奇数剩一个位置出来怎么办？那就O(n)枚举一遍找到可行的位置和它换一下即可，易

link：https://codeforces.com/contest/1630/problem/F给你一个由\(n\)个顶点组成的无向图，编号从\(1\)到\(n\)，其中顶点\(i\)的值为\(a_i\)，所有值\(a_i\)都是不同的。如果\(a_u\)整除\(a_v\)，则两个顶点\(u\)和\(v\)之间存在一条边。当删除一个顶点时，也就删除了

朴素算法不必多说，\(O(n^2)\)的暴力dp转移。优化算法时间为\(O(n\logn)\)，本质是贪心，不是dp。思路是维护一个单调栈（手写版），使这个栈单调不降。当该元素\(\ge\)栈顶元素时，把这个元素压入栈中。否则，在单调栈中找到第一个大于该元素的项，把这一项改为这个元素。（因为要

题目传送门分析首先，可以放在一起当且仅当\(\max\{a_i,a_j\}\&\min\{a_i,a_j\}\neq\min\{a_i,a_j\}\)根据Dilworth定理可知最小链划分中链的数目等于最长反链的长度所以设\(dp[i]\)表示以\(i\)为结尾的反链的最大长度，则\(dp[i]=\max_{j|i}\{dp[j]\}+[a_k==i]\)

偏序集对于一个偏序集\(D\)，我们有一些定义比较:定义\(D\)中的两个元素\(X,Y\)，如果$\foralli,X_i<=Y_i$，则称\(X,Y\)两个元素可比，且\(X\)小于等于\(Y\)

偏序关系对于二元关系\(R\subseteqS\timesS\)，若\(R\)是自反的，反对称的，传递的，那么\(R\)称为偏序关系。自反性\(a\preceqa，\foralla\inS\)反对称性\(\foralla，b\i

Dilworth定理偏序集能划分成的最少的全序集个数等于最大反链的大小。名词解释偏序在集合\(S\)中定义的二元关系\(\le\)，如果它满足以下三个性质：自反性：\(\forallx

Dilworth定理对于偏序集\(D\)，我们有若干概念：链：\(D\)中的一个子集\(C\)满足\(C\)中任意两个元素都可比，即构成全序集。反链：\(D\)中的一个子集\(B\)满足\(B\)