昨天晚上没打，今天来看一看题
错失上 (rating) 好机会
我们把这道题看成两部分
第一部分：计算出选每个线段能获得的权值
第二部分：根据第一部分的结果 (DP)
第二部分很好求，这道题的难点主要在第一部分
我们将区间按照长度排序，对于每一个区间做一次与第二部分类似的 (DP)
就可以得到选每个线段能得到的权值
然后 (DP) 就可以了
代码（我的实现有点鬼畜）
#include<bits/stdc++.h>
#include <cstdio>
clock_t clk=clock();
namespace IO
{
using namespace std;
char buf[1<<22],Out[1<<22],*p1=buf,*p2=buf;
int p3=-1,f=0;
inline void file()
{
#ifdef NTFOrz
freopen("file.in","r",stdin);
#endif
}
inline char getchar()
{
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline void flush(){fwrite(Out,1,p3+1,stdout),p3=-1;}
inline void check(){if (p3>(1<<21)) flush();}
inline void putchar(char a){Out[++p3]=a;check();}
inline void put(string s)
{
int tmp=p3;
while (p3-tmp<s.size()) putchar(s[p3-tmp]);
}
inline char gc()
{
char c=getchar();
while (!c||c=='
'||c==' ') c=getchar();
return c;
}
inline void getc(char *ch)
{
char c=getchar();int p=-1;
while (!c||c=='
'||c==' ') c=getchar();
while (!(!c||c=='
'||c==' ')) ch[++p]=c,c=getchar();
}
inline void chktime()
{
#ifdef NTFOrz
printf("%dms
",clock()-clk);
#endif
}
}
namespace my_std
{
using namespace std;
#define getchar IO::getchar
#define putchar IO::putchar
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#define Re register
#define rep(i,a,b) for (Re int i=(a);i<=(b);i++)
#define drep(i,a,b) for (Re int i=(a);i>=(b);i--)
#define repv(i,v) for (Re int i=0;i<v.size();i++)
#define go(u) for (Re int i=head[(u)];i;i=e[i].nxt)
#define writesp(x) write(x),putchar(' '),IO::check()
#define writeln(x) write(x),putchar('
'),IO::check()
#define mem(x,v) memset(x,v,sizeof(x))
#define pb push_back
#define fir first
#define sec second
#define MP make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int INF=0x7fffffff;
inline int read()
{
int sum=0,f=0;char c=getchar();
while (!isdigit(c)) f|=(c=='-'),c=getchar();
while (isdigit(c)) sum=(sum<<1)+(sum<<3)+(c^48)%998244353,c=getchar();
return f?-sum:sum;
}
void write(int k)
{
if (k<0) putchar('-'),k=-k;
if (k>=10) write(k/10);
putchar(k%10+48);
}
#define templ template<typename T>
templ inline void chkmax(T &x,T y){if (x<y) x=y;}
templ inline void chkmin(T &x,T y){if (x>y) x=y;}
mt19937 rng(time(NULL));
templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
}
using namespace my_std;
const int N=300010;
int n,m,f[N];
vector<pii>v[N];
vector<int>vv[N];
struct node{int l,r,val;}p[N];
inline bool cmp1(node a,node b){return a.l<b.l;}
inline bool cmp2(node a,node b){return a.r<b.r;}
inline bool cmp3(node a,node b){return a.r-a.l<b.r-b.l;}
int main()
{
IO::file();
int T=read();
while (T--)
{
n=read(),m=0,mem(f,0);
rep(i,1,n) p[i].l=read(),p[i].r=read(),p[i].val=0,chkmax(m,p[i].r);
rep(i,1,m) v[i].clear(),vv[i].clear();
sort(p+1,p+n+1,cmp3);
rep(i,1,n) vv[p[i].r].pb(i);
rep(i,1,n)
{
mem(f,0);
int l=p[i].l,r=p[i].r;
rep(j,l,r)
{
f[j]=f[j-1];
repv(k,vv[j])
{
if (p[vv[j][k]].l>=l&&(k!=r||p[vv[j][k]].l!=l))
{
chkmax(f[j],f[p[vv[j][k]].l-1]+p[vv[j][k]].val);
}
}
}
p[i].val=f[r]+1;
}
mem(f,0);
rep(i,1,n) v[p[i].r].pb(MP(p[i].l,p[i].val));
rep(i,1,m)
{
f[i]=f[i-1];
repv(j,v[i])
{
int l=v[i][j].fir,w=v[i][j].sec;
chkmax(f[i],f[l-1]+w);
}
}
writeln(f[m]);
}
IO::flush();
IO::chktime();
return 0;
}