这题是一道状态压缩 我们定义一个二进制数 sum 来表示每个点 (0 n−1) 是否被连过边 再定义一个 x 为所连接到的最后一个点 显然dpsum,x满足最优子结构，于是就可以 dp 了 接下来考虑 dp 的转移，这显然十分容易 对于每一个 i∈[1,n] 我们只需 for 一遍当前所有的边 而后判断是否有一条边与之相交即可 若点 A 的编号在点C和点 D 之间，点B的编号在点 C 和点D之外 则线段 AB 与线段 CD 相交 当然由于最后一个点要与第一个点相连，最后还需要判一下最后一个点的编号是否为 n <script type="math/tex" id="MathJax-Element-301">n</script> 代码如下：
#include<bits/stdc++.h> using namespace std; #define M 18 #define ll long long ll dp[1<<M][M]; struct node{ int x,y; }stk[M+5]; int n,q,top,p; ll dfs(int sum,int x){ if(sum==(1<<n)-1)return (x+1)%n!=q&&(q+1)%n!=x;//所有边已连完 ll &res=dp[sum][x]; if(res)return res; for(int i=0;i<n;i++){ if(sum&(1<<i))continue; for(int j=1;j<top;j++) if(i>stk[j].x&&i<stk[j].y&&(x<stk[j].x||x>stk[j].y)||(i<stk[j].x||i>stk[j].y)&&x>stk[j].x&&x<stk[j].y){//相交 stk[++top]=(node){min(x,i),max(x,i)};//用栈储存当前边 res+=dfs(sum|(1<<i),i); top--; break; } } return res; } int main(){ int m,sum=0; scanf("%d %d",&n,&m); int x; for(int i=1;i<=m;i++){ scanf("%d",&x); x--; if(i==1)q=x; else stk[++top]=(node){min(p,x),max(p,x)}; p=x; sum|=1<<x; }//先连完最初的边 cout<<dfs(sum,x)<<endl; return 0; }