C++14(g++5.4) 解法, 执行用时: 638ms, 内存消耗: 238468K, 提交时间: 2020-08-15 17:07:13

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2e5+5;
ll n, m,ans=-1,dp[maxn][150];
vector<ll >ve ;
struct node
{
    ll l, r, c;
    bool operator< (const node& v)const{
        return r < v.r;
    }
}a[maxn];

int main() {
    
    cin >> n >> m;
    for(ll i = 1; i <= n; i++)
    cin>>a[i].l>>a[i].r>>a[i].c; 
    sort(a+1, a+1+n);
    for(ll i = 1; i <= n; i++) ve.push_back(a[i].r);
    memset(dp, -1, sizeof(dp));  
    dp[0][0] = 0;   
    for(ll i = 1; i <= n; i++){
    for(ll j = 0; j < 128; j++)
	{ 
    dp[i][j] = max(dp[i-1][j], dp[i][j]);
    ll pos = upper_bound(ve.begin(), ve.end(), a[i].l-1)-ve.begin();
    if(dp[pos][j] != -1)
    dp[i][j|(1<<(a[i].c-1))]=max(dp[i][j|(1<<(a[i].c-1))], dp[pos][j]+a[i].r-a[i].l);       
     if (__builtin_popcount(j) == m) ans = max(ans, dp[i][j]);          
        }
    } 
    cout<<ans<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 146ms, 内存消耗: 53188K, 提交时间: 2020-07-30 17:25:02

#include<bits/stdc++.h>
#define nx 100005
using namespace std;
struct node{
	int l,r,c,len;
	bool operator < (const node &x)const{
		return r<x.r;}
}p[nx];
int n,m,a[nx],dp[nx][130];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>p[i].l>>p[i].r>>p[i].c,--p[i].c,p[i].len=p[i].r-p[i].l;
	sort(p+1,p+1+n);
	for(int i=1;i<=n;++i)a[i]=p[i].r;
	memset(dp,128,sizeof dp),dp[0][0]=0;
	for(int i=1;i<=n;++i){
		int x=lower_bound(a+1,a+1+n,p[i].l)-a-1,now=1<<p[i].c;
		for(int j=0;j<128;++j){
			dp[i][j]=dp[i-1][j];
			if(now&j)dp[i][j]=max(dp[i][j],max(dp[x][j]+p[i].len,dp[x][j^now]+p[i].len));
		}	
	}
	int ans=0;
	for(int i=1;i<128;++i)
		if(__builtin_popcount(i)==m)ans=max(ans,dp[n][i]);
	cout<<(ans?ans:-1);
}