C++ 解法, 执行用时: 319ms, 内存消耗: 9892K, 提交时间: 2021-11-23 21:36:28

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
struct node{
	int s,t,c;
}no[N];
bool cmp(node a,node b){
	return a.s<b.s;
}
int pos[2][16][5]; //µÚi´Î½áÊøºó¶ÔӦ״̬µÄ¶ÔÓ¦ÊÖÖ¸µÄλÖà 
int kuai[2][16][5]; //ÊÖÖ¸°´µÄÊǵڼ¸¸ö¿é 
int val[5]={0,1,2,4,8}; //ÿ¸öλÖõÄȨֵ 
int dp[2][16];
bool used[5];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d %d",&no[i].s,&no[i].t,&no[i].c);
	}
	sort(no+1,no+1+n,cmp);
	int up = 1<<4; //״̬´Ó0~up-1
	dp[0][0]=1;
	int cur=0;
	for(int i=1;i<=n;i++)
	{
		cur^=1;
		memset(dp[cur],0,sizeof dp[cur]);
		memset(pos[cur],0,sizeof pos[cur]);
		memset(kuai[cur],0,sizeof kuai[cur]);
		for(int j=0;j<up;j++) //ÉÏÒ»´ÎµÄ״̬ 
		{
			if(dp[cur^1][j]==0) continue;
			//ÉϴεÄ״̬µ½ÏÖÔڻᷢÉú±ä»¯
			int now=0; //ÏÖÔÚµÄ״̬(»¹Ã»Óа´ÏµÚi¸ö)
			//ÅжÏÿ¸ùÊÖÖ¸µ½ÏÖÔÚµÄÊÇ·ñ±»ÊÍ·Å 
			for(int k=1;k<=4;k++) //ÊÖÖ¸ 
			{
				if(pos[cur^1][j][k]==0) now+=0,used[k]=0; //used[k]==0 ±íÃ÷±¾´Î¿ÉÒÔʹÓÃkÕâ¸ùÊÖÖ¸ 
				else
				{
					if(no[kuai[cur^1][j][k]].t <= no[i].s) //µÚk¸öÊÖÖ¸ÔÚµ±Ç°Õâ¸ö¿ªÊ¼Ö®Ç° ÒѾ­½â·Å 
					{
						now+=0,used[k]=0;
					}
					else now+=val[k],used[k]=1;
				}
			}
			for(int k=1;k<=4;k++) //ÓõÚk¸ùÊÖָȥ°´µÚi¸ö 
			{
				if(used[k]==1) continue;
				//ÅжÏÓõÚk¸ùÊÖָȥ°´µÚi¸öÊÇ·ñºÏ·¨ 
				bool f=true;
				for(int x=1;x<=4;x++)
				{
					if(k==x) continue;
					if(used[x])
					{
						if(x<k && pos[cur^1][j][x]>no[i].c) f=false;
						else if(x>k && pos[cur^1][j][x]<no[i].c) f=false;
					}
				}
				if(f)
				{
					dp[cur][now+val[k]]=1;
					for(int x=1;x<=4;x++)
					{
						if(x==k) pos[cur][now+val[k]][x]=no[i].c,kuai[cur][now+val[k]][x]=i;
						else
						{
							if(used[x]) pos[cur][now+val[k]][x]=pos[cur^1][j][x],kuai[cur][now+val[k]][x]=kuai[cur^1][j][x];
							else pos[cur][now+val[k]][x]=0,kuai[cur][now+val[k]][x]=0;
						}
					}
				} 
			}
		}
	} 
	bool f=false;
	for(int i=0;i<up;i++) if(dp[cur][i]) f=true;
	if(f) printf("Yes");
	else printf("No");
}
/*

5
1 5 1
2 6 2
3 7 3
4 8 4
5 9 5

no*/