一道毒瘤的 状态压缩 DP 题。
题目链接:Luogu P4460/LibreOJ 2536/BZOJ 5299/CQOI 2018 D2T1。
题目
题目描述
自己去看。
题解
思路
观察到 $n$ 比较小,考虑 状态压缩 DP。
设 $\text{dp} _ {S,i}$ 表示二进制下选取的点的状态 $S$,以及最后一个点的编号为 $i$,得到路径的条数,那么我们有状态转移方程:
$$\text{dp} _ {S,i}=\sum _ {j \in S , (i,j) \text{不被阻挡} } \text{dp} _ {S-j,j}$$
记得提前预处理会不会被阻挡。
另外提醒本题模数是 $10^8+7$,不要打错了。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define MOD 100000007 //注意模数是 1e8+7
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool cnt=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)cnt|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return cnt?-res:res;
}
const int MAXN=20;
int n;
struct Point{
int x,y;
inline void Read(void){
x=read(),y=read();
return;
}
};
int R[MAXN][MAXN];
int dp[1<<MAXN][MAXN];
int cnt[1<<MAXN]; //cnt[i] 表示 i 的二进制表示下 1 的个数
Point p[MAXN];
inline bool check(const Point& l,const Point& mid,const Point& r){ //判断 l 到 r 的路径是否被 mid 阻挡
return ((r.x-l.x)*(mid.y-l.y)==(r.y-l.y)*(mid.x-l.x))&&((mid.x-l.x)*(mid.x-r.x)<0||(mid.y-l.y)*(mid.y-r.y)<0);
}
int main(void){
n=read();
for(reg int i=0;i<n;++i)
p[i].Read();
for(reg int i=1;i<(1<<n);++i)
cnt[i]=cnt[i>>1]+(i&1); //统计 1 的个数
for(reg int i=0;i<n;++i)
for(reg int j=0;j<n;++j)
if(i!=j)
for(reg int k=0;k<n;++k)
if(k!=i&&k!=j)
if(check(p[i],p[k],p[j]))
R[i][j]|=(1<<k); //从 i 到 j 会被 k 阻挡
for(reg int i=0;i<n;++i)
dp[1<<i][i]=1; //临界状态
reg int ans=0;
for(reg int S=1;S<(1<<n);++S){
for(reg int j=0;j<n;++j)
if(dp[S][j]&&((S>>j)&1)){
if(cnt[S]>=4)
ans=(ans+dp[S][j])%MOD;
for(reg int k=0;k<n;++k)
if(((S>>k)&1)||(R[j][k]&S)!=R[j][k])
continue; //如果 S 里面选了 k 或者 j 到 k 被阻挡,则跳过
else
dp[S|(1<<k)][k]=(dp[S|(1<<k)][k]+dp[S][j])%MOD;
}
}
printf("%d\n",ans); //输出答案
return 0;
}
近期评论