自动搬运

查看原文

来自洛谷，原作者为

	孙子隆 **

搬运于2025-08-24 22:00:25，当前版本为作者最后更新于2019-09-25 19:27:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本应该10.1前停课的我，选择提早来腾飞。

首先看到这个题，题面就很有意思。

n<20!

显然首先应该想到就是状压了吧

设置dp[i]表示到达i状态得所有情况和

然后接着去想怎么转移和判断是否能够表示这些状态。

然后我发现我失败了，开一维的话没法转移， 因为时间复杂度会妥妥的T飞。

然后想一下（1<<20）并不大，可以考虑开两维。

设置dp[i][j]表示到达i状态后最后一个点是j的所有情况。

然后枚举每一个现阶段的点i和要转移的点k，然后枚举每一个状态。这样时间复杂度是 O(2^n*n^2）

最大的情况是约是4*1e8，

这样按照ccf的老爷机要跑4s。

这样我只能是吸氧过

转移方程也不难写 dp[i|(1<<(k-1)][k]+=dp[i][j]; 这个题在判断添加上很像P2831

其余优化小细节都在代码里 （本代码借鉴第一页大佬的代码）

然后我写到一半省队爷突然回来，然后我问他是否吸了o2，然后我得知他通过二进制成功AC不开氧气

下面我贴一下他代码吧原理是一样的

二进制卡常还是nb啊！！！！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Mod 100000007
using namespace std;
int nd[21][21];
int dp[1<<20][20];
int f[1<<20];
int n;
struct Point{
	int x,y;
}p[21];
bool is(Point a,Point b,Point c)//b是否在a和c连线上
{
	return (a.x-b.x)*(b.y-c.y)==(b.x-c.x)*(a.y-b.y);
}
int main()
{
//	freopen("android.in","r",stdin);
//	freopen("android.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d %d",&p[i].x,&p[i].y);
	for(int i=1;i<(1<<n);i++)
		f[i]=f[i>>1]+(i&1);
	int ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(i==j)continue;
			for(int k=0;k<n;k++)
			{
				if(k==i||k==j)continue;
				if(((p[k].x-p[i].x)*(p[k].x-p[j].x)<0||(p[k].y-p[i].y)*(p[k].y-p[j].y)<0)&&is(p[i],p[k],p[j]))
					nd[i][j]|=(1<<k);
			}
		}
	for(int i=0;i<n;i++)
		dp[1<<i][i]=1;
	for(int i=1;i<(1<<n);i++)
	{
		for(int j=0;j<n;j++)
			if(dp[i][j]&&((1<<j)&i))
			{
				if(f[i]>=4)ans=(ans+dp[i][j])%Mod;
				for(int k=0;k<n;k++)
					if(!((1<<k)&i)&&(nd[j][k]&i)==nd[j][k])
					{
						dp[i|(1<<k)][k]=(dp[i|(1<<k)][k]+dp[i][j])%Mod;
					}
			}
	}
	printf("%d\n",ans);
//	fclose(stdin);fclose(stdout);
	return 0;
}

一定要事先预处理会省很多时间！！！