暴力部分

除了$n\leq 10$的部分分以外，其他部分都需要多多少少用到正解。

$n\leq 10$的时候，我们可以大力爆搜划分的方式，具体策略可以是：我一开始用$n$个单点的区间，然后每次枚举相邻的两个区间，把他们合并成一个区间，然后继续搜索下去，直到他们合成$[1,n]$为止。

总的方案数显然可以用一个$dp$来计算：$dp_n=\sum dp_l dp_{n-1-l}$，典型的卡特兰数。

搜完以后就可以直接枚举每个区间去计算答案了。

正解

我们考虑这样一件事：$f_{l,r}$的下界是$1$，这是显然的。

什么时候会让$f_{l,r}$增加呢？

当且仅当，当前线段树上有一个区间$[L,R]$，这个区间$[L,R]$跟$[l,r]$有交集，但是又不是包含关系（这样说明你一定会在查询的时候进入$[L,R]$这个节点）；你从$k(L\leq k<R)$处把这个区间划分开了，而$k$满足$l\leq k<r$。

这时候，你必定会递归$[L,R]$的两边子树，那每个子树至少会产生一个代价，答案的下界就增加了$1$。

所以结论是，在你查询的过程中，“双边递归”的次数就是查询到的区间个数了。

所以我们就可以按照线段树上节点被“双边递归”的次数来dp了。

$dp_{l,r}$表示当前线段树上的区间是$[l,r]$，你把它划分完毕后，内部被双边递归的最小总次数。

$dp_{l,r}=\min_{k=l}^{r-1}(dp_{l,k}+dp_{k+1,r}+cost(l,r,k))$。

$cost(l,r,k)$指的是，有多少个查询的区间，和$[l,r]$有交集，但不是包含关系，且经过了位置$k+0.5$。

这个可以被简化成：有多少个查询的区间，经过了$[k+0.5]$，且跟$[l,r]$不是包含关系。

我们可以预处理$w[k]$表示有多少个区间经过了$k+0.5$这个位置。

预处理$num[l][r]$表示有多少个查询的区间包含了$[l,r]$。

然后用$w[k]-num[l][r]$来代表答案。

$num[l][r]$可以用类似二维前缀和的思路来做，包含了$[l,r]$的区间个数，等于包含了$[l-1,r],[l,r+1]$的区间个数，减去包含了$[l-1,r+1]$的区间个数，再加上区间$[l,r]$的个数。按区间大小从大到小做即可。

最后的时间复杂度：$O(n^3)$。

#include<bits/stdc++.h>
#define ll long long
#define maxn 505
using namespace std;
int n,Q;
int w[maxn]; //经过[i+0.5]这个位置的区间有多少个 
int num[maxn][maxn]; //包含这个区间的区间有多少个 
int l,r; 
ll dp[maxn][maxn];
int main()
{
	cin>>n>>Q;
	for (int i=1;i<=Q;i++)
	{
		cin>>l>>r; num[l][r]++;
		w[l]++; w[r]--;
	}
	for (int i=1;i<=n;i++) w[i]+=w[i-1];
	for (int len=n-1;len>=1;len--)
	for (int l=1;l+len-1<=n;l++)
	{
		int r=l+len-1;
		num[l][r]=num[l][r]+num[l-1][r]+num[l][r+1]-num[l-1][r+1];
	}
	
	for (int len=2;len<=n;len++)
	for (int l=1;l+len-1<=n;l++)
	{
		int r=l+len-1;
		dp[l][r]=1ll<<60;
		for (int k=l;k<r;k++)
		{
			dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+(w[k]-num[l][r]));
		}	
	}
	cout<<dp[1][n]+Q<<endl;
}