题目

给你若干条线段，可以进行若干次操作，选择两条线段\(i\)和\(j\)，满足\(R_i<L_j\)，将\(j\)接到\(i\)的后面（此时必须要满足\(i\)必须后面没有接线段，\(j\)必须前面没有接线段）。
操作一定要进行到不能继续操作为止。
问最终形成的图的方案数。
\(n\leq 300\)

思考历程

首先我理解错了题意，认为只需要接出一条链……
然后知道真正的题意是读题一个小时后的事情。
u1s1，DYP坐在附近特别容易让人心态爆炸。
人家随随便便切的题，我三个钟都想不出来。
甚至开始思考人生

想到的最优的做法就是状压DP，不讲。

正解

对于一个线段，将它的左端点和右端点分开处理，其实对答案没有任何影响。
于是问题变成了：有若干个左端点和右端点，要用左边的右端点匹配右边的左端点，匹配到不能匹配为止。
然后就是个DP问题：\(f_{i,j,k}\)表示前\(i\)个点，可以选的点有\(j\)个，必须选的点有\(k\)个（当某个左端点不选时，左边的所有可选的右端点都要变为必须选）
\(O(n^3)\)

代码

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 310
#define ll long long
#define mo 1000000007
int n,m;
struct DOT{
	int x;
	bool ty;
} d[N*2];
bool cmpd(DOT a,DOT b){return a.x<b.x || a.x==b.x && a.ty<b.ty;};
ll f[N*2][N][N];
int main(){
	freopen("ds.in","r",stdin);
	freopen("ds.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		int l,r;
		scanf("%d%d",&r,&l);
		d[++m]={r,1};
		d[++m]={l,0};
	}
	sort(d+1,d+m+1,cmpd);
	f[0][0][0]=1;
	for (int i=0;i<m;++i)
		if (d[i+1].ty==0){
			for (int j=0;j<=i && j<=n;++j)
				for (int k=0;k<=j;++k){
					ll tmp=f[i][j][k];
					if (tmp){
						if (k) (f[i+1][j-1][k-1]+=(ll)tmp*k)%=mo;
						if (j>k) (f[i+1][j-1][k]+=(ll)tmp*(j-k))%=mo;
						(f[i+1][j][j]+=tmp)%=mo; 
					}
				}
		}
		else{
			for (int j=0;j<=i && j<=n;++j)
				for (int k=0;k<=j;++k){
					ll tmp=f[i][j][k];
					if (tmp)
						(f[i+1][j+1][k]+=tmp)%=mo;
				}
		}
	ll ans=0;
	for (int j=0;j<=n;++j)
		(ans+=f[m][j][0])%=mo;
	printf("%d\n",ans);
	return 0;
}

总结

见到一些整体的对象，可以考虑一下将对象的局部分开处理。

6654. 【2020.05.27省选模拟】数据结构

原文：https://www.cnblogs.com/jz-597/p/12989660.html