题目：


输入样例：
4 2
1 3 1
4 5 1
5 8 2
7 9 3
输出样例：
5

挺恶心的一道题，我们用dp来解决，dp[i][j]代表什么，i代表前i个线段，j代表的是颜色（由1-2^7-1组成，其中二进制表示为1的位置就是j所含有的颜色),
举个例子，j = 5，用二进制表示就是101第一个位置和第三个位置有1，那么5就代表含有颜色1和3，为什么这么设置状态，就是你可以通过上一个状态去更新目前的状态，假如i的上一个可更新点是t（不接触），两种可能，一种i这个点可能是一种新的颜色，而又可能是老的颜色，

（1 << (a[i].c - 1)的意思是去除j中第c个位置的1）
如果前面没有这个颜色那么我们就用下面的转移方程：

if (dp[t][j - (1 << (a[i].c - 1))] != -1)	
dp[i][j] = max(dp[i][j], dp[t][j - (1 << (a[i].c - 1))] + a[i].r - a[i].l);

如果前面有这个颜色我们就用这个方程：

if (dp[t][j] != -1)		
dp[i][j] = max(dp[i][j], dp[t][j] + a[i].r - a[i].l);

整体来说就是二进制枚举，关于二进制枚举可以看这个文章：二进制枚举

最后代码就是：

#include <bits/stdc++.h>
using namespace std;const int mn = 100000;struct node
{int l, r, c;
} a[mn];
bool cmp(const node& a, const node& b)
{return a.r < b.r;
}	/// 按右边界排序int dp[mn][150];
int main()
{int n, m;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d %d %d", &a[i].l, &a[i].r, &a[i].c);sort(a + 1, a + n + 1, cmp);memset(dp, -1, sizeof dp);a[0].l = a[0].r = a[0].c = 0;dp[0][0] = 0;for (int i = 1; i <= n; i++){int t = 0;int l = 0, r = i - 1;while (l <= r){int mid = (l + r) / 2;if (a[mid].r < a[i].l){l = mid + 1;t = mid;}elser = mid - 1;}	/// 二分查找不接触的前一条线段for (int j = 0; j < (1 << 7); j++)	/// 二进制枚举前i条线段选择的颜色情况{if (dp[i - 1][j] != -1)dp[i][j] = dp[i - 1][j];	// 不选择当前线段if ((j >> (a[i].c - 1)) & 1)	// 该色在枚举颜色范围内 可选{if (dp[t][j - (1 << (a[i].c - 1))] != -1)	// 前 t 条无当前色dp[i][j] = max(dp[i][j], dp[t][j - (1 << (a[i].c - 1))] + a[i].r - a[i].l);if (dp[t][j] != -1)		// 前 t 条已经有当前色dp[i][j] = max(dp[i][j], dp[t][j] + a[i].r - a[i].l);}}}int ans = 0;for (int i = 0; i < (1 << 7); i++) // 枚举所有组合出的颜色情况{int t = 0;for (int j = 0; j < 7; j++)if (i >> j & 1)t++;if (t == m)	//选择了 m 种颜色ans = max(ans, dp[n][i]);}if (ans == 0)cout << "-1" << endl;elsecout << ans << endl;
}