Description
给定 \(n\) 个区间，选择至多 \(k\) 个区间，使得被覆盖的元素的个数最多。求最大值。\(1\leq l\leq r\leq n\)。
Solution
赛场上想的是用区间定义状态，先把区间按右端点排序，\(dp_{i,k}\) 表示考虑前 \(i\) 个区间，选了其中 \(k\) 个，且第 \(i\) 个区间必选的最大值。那么就要分为有交集和无交集两种转移方式，\(dp_{i,k}=[r_j<l_i](dp_{j,k-1}+r_i-l_i+1)+[r_j>=l_i](dp_{j,k-1}+r_i-r_j)\)。会发现是一个二位偏序，避免不了线段树。
更直接的状态定义是考虑用位置做状态，\(dp_{i,k}\) 表示考虑到第 \(i\) 个位置，已经选了 \(k\) 个区间的最大值。那么 \(dp[i][k]=\max\{dp[L_i-1][k-1]+i-L_i+1,dp[i-1][k]\}\)，其中 \(L_i\) 表示所有覆盖点 \(i\) 的区间的左端点的最小值。暗含了一个贪心。
标签：最大值,Alice,leq,Stamps,区间,dp From： https://www.cnblogs.com/wwlwQWQ/p/17753141.html