2023 qbxt 笔记整理

洛谷P4460

n<20,试试状压

设 \(dp[i][j]\) 表示状态为i,最后一个点为j（当前在点j）。

枚举当前点为i，要转移的点为k

转移：$ dp[i|(1<<k-1)][k]+=dp[i][j] $

还需要判断一下三点连线在不在同一条直线上。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x=0,f=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}
void print(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+48);
}
const int Mod=1e8+7;
int n,m,dp[1<<20][20],ans;
int f[1<<20];
int map1[51][51];
int x[51],y[51];
bool ss(int a,int b,int c) {
	return ((x[a]-x[b])*(y[b]-y[c])==(x[b]-x[c])*(y[a]-y[b]));
}
signed main(){
    n=read(); 
    for (int i=0;i<n;++i) {
    	x[i]=read(); y[i]=read();
	}
	for (int i=1;i<(1<<n);++i) {
		f[i]=f[i>>1]+(i&1);
	}
	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 ((((x[k]-x[i])*(x[k]-x[j])<0)||((y[k]-y[i])*(y[k]-y[j])<0))&&ss(i,k,j)) {
				    map1[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)&&(map1[j][k]&i)==map1[j][k]) {
	    	    		dp[i|(1<<k)][k]=(dp[i|(1<<k)][k]+dp[i][j])%Mod;
					}
				}
			}
		}
	}
	cout<<ans;
	return 0;
}