学习笔记[AGC039E] Pairing Points

太复杂了，做不动。

设第$2n$个点与$k$相连，这样把点分成了左右两个集合，一定存在左边的$x$与右边的$y$相连的一条边，并且这个结构有一个比较优美的性质，左右相连的边的点的编号应该是单调，否则会存在环。那么我们取最靠近上端的那条边。

那么我们用$[i:j](k)$表示$[i:j]$这一段圆弧，$k$向圆弧外的一个点连了边的方案数。如果我们直接将问题拆分成$[i:k-1](x)$和$[k1:j](y)$那么显然这样的方案是合法的，因为任意一条边都能和$(x,y)$互达并且不存在环。显然我们只遗漏了$x$下端点和$y$下端点连边的情况，而我们事实上可以选择一条割线，使得将$(?,k)$删去后变成不连通的两部分，更形象的讲，删去$(?,k)$后与$(x,y)$联通的一定是上端两段圆弧，那么枚举$p$,$q$，显然$p$,$q$上端只存在$(x,y)$一条横边，那么可以拆分成$[i:p](x)$和$[q:j](y)$，下端圆弧因为不存在向上的边因此直接拆成$[p1:q-1](k)$。

复杂度 O ( n 7 ) O(n^7) O(n7)。据说常数极小。

#include<bits/stdc  .h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define db long double
#define cpx complex<db>
using namespace std;
int n;
char a[45][45];
ll dp[45][45][45],res;
ll dfs(int i,int j,int k){
	if(k<i||k>j)return 0;
	if(i==j)return 1;
	if(i==k||j==k)return 0;
	if(~dp[i][j][k])return dp[i][j][k];
	ll res(0);
	for(int x=i;x<k;x  ){
		for(int y=k 1;y<=j;y  ){
			if(a[x][y]=='1'){
				for(int p=x;p<k;p  ){
					for(int q=k 1;q<=y;q  ){
						res =dfs(i,p,x)*dfs(q,j,y)*dfs(p 1,q-1,k);
					}
				}
			}
		}
	}
	return dp[i][j][k]=res;
}
int main(){
	memset(dp,-1,sizeof dp);
	scanf("%d",&n),n<<=1;
	for(int i=1;i<=n;i  ){
		scanf("%s",a[i] 1);
	}for(int i=1;i<n;i  )if(a[n][i]=='1')res =dfs(1,n-1,i);
	printf("%lld",res);
}

这篇好文章是转载于：学新通技术网