CF1399F Yet Another Segments Subset

一道不是很难的区间DP题，我竟然没能想到。

由于这道题的空间限制，我们先离散化。

设 (f_{l,r}) 表示区间 ([l,r]) 内最多可以选择多少线段。若：

1. 没有以 (l) 为左端点的线段，则 (f_{l,r}=f_{l+1,r})；
2. 遍历这些线段并设当前线段的右端点为 (r')，则 (f_{i,j}=min{tmp+f_{i,r'}+f_{r'+1,r}})，其中 (tmp) 表示是否存在左端点为 (l)，右端点为 (r) 的线段。

实现时注意一点边界就可以通过。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

const int N=6009;
int n,l[N],r[N],cnt,b[N],f[N][N];
vector <int> pos[N];

void init()
{
	scanf("%d",&n);cnt=0;
	for (int i=1;i<=n;i++)
		scanf("%d %d",&l[i],&r[i]),b[++cnt]=l[i],b[++cnt]=r[i];
	sort(b+1,b+1+cnt);
}

int dp(int l,int r)
{
	if(f[l][r]!=-1) return f[l][r];
	f[l][r]=0;
	int flag=count(pos[l].begin(),pos[l].end(),r);
	f[l][r]=max(f[l][r],flag+(l==r?0:dp(l+1,r)));
	for (int i=0;i<pos[l].size();i++)
	{
		int j=pos[l][i];
		if(j>=r) continue;
		f[l][r]=max(f[l][r],flag+dp(l,j)+(j==r?0:dp(j+1,r)));
	}
	return f[l][r];
}

void work()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		init();
		cnt=unique(b+1,b+1+cnt)-b-1;
		for (int i=1;i<=cnt;i++)
		{
			pos[i].clear();
			for (int j=1;j<=cnt;j++)
				f[i][j]=-1;
		}
		for (int i=1;i<=n;i++)
			l[i]=lower_bound(b+1,b+1+cnt,l[i])-b,
			r[i]=lower_bound(b+1,b+1+cnt,r[i])-b,
			pos[l[i]].push_back(r[i]);
		printf("%d
",dp(1,cnt));
	}
}

int main()
{
	work();
	return 0;
}