真是太神了orz
我们先贪心地把被包含的线段删掉，把剩下的线段按左端点排序，这样的话右端点显然也是有序的。
设dp[i][k],表示前i个线段,删了k个,且必须保留i线段的最大覆盖长度。枚举上一个线段的位置j，那么我们有转移.
dp[i][k]=max{dp[j][k−(i−j−1)]+w(i,j)}dp[i][k]=\bold m\bold a\bold x \{dp[j][k-(i-j-1)]+w(i,j)\}dp[i][k]=max{dp[j][k−(i−j−1)]+w(i,j)}
w(i,j)表示把线段i接在线段j后面增加的长度。 这样的复杂度是O(nk2)O(nk^2)O(nk2)的，需要优化。
我们发现如果dp[x][y]能够转移到dp[i][j]，则有j=y+i-x-1，即x-y=i-j-1.因此我们在转移dp[i][j]时，所有的决策就是满足x-y=i-j-1的dp[x][y]，并且分成两类：
1、线段x，i不相交，则w(i,j)=len[i]，我们只需维护所有不相交的最大的dp[x][y]即可。
2、线段x，i相交，则贡献为dp[x][y]+b[i].r-b[x].r，我们维护dp[x][y]-b[x].r的最大值即可。
我们用n个单调队列来维护即可。
AC代码
欢迎加入团队
