PolygonTraversal2
题意 :
给你一个n个节点的正n边形,然后你有已经走了几步,你要接着走下去,每一步是连接两个节点,你走的每一步都要和之前的走过的线相交,最后一步回到起点。。。问有几种方案。。。
分析 :
因为n小于13,所以直接状压一下,然后枚举最后一步走到的点,然后枚举一个可以到达的点走下去。如何判断两个点的连线会和之前的线相交呢,我们只要满足这两个点把图形分成的两部分都有走过的点就好啦。。。
代码 :
int dp[1<<14][15];
vector <int> show[15];
void init(int now, const vector<int> & vec)
{
for(int i=0;i<=now;i++)
show[i].clear();
for(int i=0;i<(1<<now);i++)
show[__builtin_popcount(i)].push_back(i);
memset(dp,0,sizeof(dp));
int start=0;
for(int i=0;i<vec.size();i++)
start|=(1<<(vec[i]-1));
show[vec.size()].clear();
show[vec.size()].push_back(start);
dp[start][vec[vec.size()-1]-1]=1;
}
int PolygonTraversal2::count(int N, vector <int> points)
{
init(N,points);
for(int i=points.size();i<=N;i++)
{
int siz=show[i].size();
for(int j=0;j<siz;j++)
{
int now=show[i][j];
for(int k=0;k<N;k++)
{
if(now&(1<<k)==0||!dp[now][k])
continue;
for(int l=0;l<N;l++)
{
if(now&(1<<l))
continue;
int flag1 = 0, flag2 = 0;
int lb = min(k, l) + 1, ub = max(k, l) - 1;
for (int ri = 0; ri < N; ri++)
if (now >> ri & 1) {
if (lb <= ri && ri <= ub) flag1 = 1;
else if (ri < lb - 1 || ri > ub + 1) flag2 = 1;
}
int flag = flag1 & flag2;
if(flag==1)
dp[now|(1<<l)][l]+=dp[now][k];
}
}
}
}
int ans=0,zz=points[0]-1;
for(int i=0;i<N;i++)
{
if(i==(zz+N-1)%N||i==(zz+N+1)%N||i==zz)
continue;
ans+=dp[(1<<N)-1][i];
}
return ans;
}
Leave A Comment