B. CannonG. League of Legends题意：给定n个区间，要求将它们分成k组，每组之间有交，最大化每组交长度之和 简化问题，对于如果一个大区间能够完整包含某个小区间，则该大区间只有两种最优决策： 单独归为一组，贡献r-l 与任意一个其包含的小区间归为一组，不对结果产生影响 可以用反证法证明结论，假如大区间和其他区间归为一组，那么将该大区间移出该组，该组的交一定不下降，再放入其包含的小区间组中，小区间所在的组的交也不下降，即大小区间在同一组的决策一定最优 于是可以把所有大区间取出来，单独讨论所有小区间，可以发现，若将剩下的区间按照左端点从小到大排序，其右端点也一定是有序的，接着考虑dp，$f[i][j]$​表示考虑前i个区间，分成j组的最优答案，而一组的贡献只与最左和最右两个区间相关，显然有转移$f[k][j+1]=\max\limits_{r[i+1]-l[k]>0} \{f[i][j]+r[i+1]-l[k]\}$     阅读全文