A – The Cow Gathering
首先，如果没有限制的话，其实从叶子结点来抽是一定有解的，可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边，初步思考可以把每个点都作为最后一个节点，然后来看新的图有没有环，这样是 \(\Theta(n^2)\)。
首先，如果没有限制的话，其实从叶子结点来抽是一定有解的，可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边，初步思考可以把每个点都作为最后一个节点，然后来看新的图有没有环，这样是 \(\Theta(n^2)\)。
先可以想到把所有的包含的区间给去掉，然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单，然而 \(k \leq 200\) 就很麻烦。