【DP计划】10.24——[BZOJ]解锁屏幕(状压DP) MEDIUM
中间鸽了好多天,但并不是我没有写题,是写完就心里憔悴,根本无心写题解了。
像淘金那种题,写完之后还能补上题解,只能说我那天心态比较好。
题目背景
使用过Android 手机的同学一定对手势解锁屏幕不陌生。Android 的解锁屏幕由3X3 个点组成,手指在屏幕上画一条线,将其中一些点连接起来,即可构成一个解锁图案。如下面三个例子所示:
画线时还需要遵循一些规则
1.连接的点数不能少于4个。也就是说只连接两个点或者三个点会提示错误。
2.两个点之间的连线不能弯曲。
3.每个点只能"使用"一次,不可重复。这里的"使用"是指手指划过一个点,该点变绿。
4.两个点之间的连线不能"跨过"另一个点,除非那个点之前已经被"使用"过了。
对于最后一条规则,参见下图的解释。左边两幅图违反了该规则:而右边两幅图(分别为2→4→1→3→6和→5→4→1→9→2)
则没有违反规则,因为在"跨过"点时,点已经被"使用"过了。
现在工程师希望改进解锁屏幕,增减点的数目,并移动点的位置,不再是一个九宫格形状,但保持上述画线的规则不变。
请计算新的解锁屏幕上,一共有多少满足规则的画线方案。
Input
输入文件第一行,为一个整数n,表示点的数目。
接下来n行,每行两个空格分开的整数xi和yi,表示每个点的坐标。
-1000≤xi,Yi≤l000,1≤n<20。各点坐标不相同
Output
输出文件共一行,为题目所求方案数除以100000007的余数。
Sample Input
4
0 0
1 1
2 2
3 3
Sample Output
8
解释:设4个点编号为1到4,方案有1→2→3→4,2→1→3→4,3→2→1→4,2→3→1→4,
及其镜像4→3→2→1,3→4→2→1,2→3→4→1,3→2→4→1.
n只有20,所以考虑状压,f[i][j]表示i为状态,j为当前状态手最后滑到的一个点。
我们再开一个cheq数组,cheq[i][j]表示从i滑到j中间需要经过那些点,然后即可进行转移。
大致题意就是这样,更多细节在下面的代码中讲述:
#include<bits/stdc++.h>
#define MD 100000007
using namespace std;
int read(){
char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-');
if(c=='-') y=-1;else x=c-'0';while(c=getchar(),c>='0'&&c<='9')
x=x*10+c-'0';return x*y;
}
int n,ans,x[24],y[24],f[1050000][23],cheq[23][23];
int check(int a,int b){
int s1=x[a]-x[b],s2=y[a]-y[b],statu=0;
for(int i=1;i<=n;i++){
if(i==a||i==b) continue;
int p1=x[i]-x[b],p2=y[i]-y[b]; //下面这三句话都是判断点是否在路径上
if(s1==0&&p1==0&&s2*p2>0&&abs(s2)>abs(p2)){statu|=(1<<i-1);continue;}
//表示两个点的纵坐标相同的情况
if(s2==0&&p2==0&&p1*s1>0&&abs(s1)>abs(p1)){statu|=(1<<i-1);continue;}
//两个点横坐标都相同的情况
if(s1&&s2&&(p1*s2==p2*s1)&&(s2*p2>0)&&(abs(s2)>abs(p2))&&(p1*s1>0)&&(abs(s1)>abs(p1))){statu|=(1<<i-1);continue;}
//两个点横纵坐标都不相同的情况,只与为什么有abs这些东西,如果不明白,向下拉看解释
}
return statu;
}
int calc(int x){
int res=0;
for(;x;x-=x&-x)res++;
return res;
}
int main()
{
n=read();
for(int i=1;i<=n;i++){
x[i]=read();y[i]=read();
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(i!=j) cheq[i][j]=cheq[j][i]=check(i,j);
for(int i=1;i<=n;i++)f[1<<i-1][i]=1;
for(int i=1;i<1<<n;i++)
for(int j=1;j<=n;j++)
if(f[i][j]){
for(int k=1;k<=n;k++)
if((i&(1<<k-1))==0&&(i|cheq[j][k])==i) //右边这句表示j到k路径上的所有点都在当前状态都被取过
f[i|(1<<k-1)][k]+=f[i][j],f[i|(1<<k-1)][k]%=MD;
}
for(int i=1;i<=(1<<n)-1;i++)
if(calc(i)>=4)for(int j=1;j<=n;j++)ans+=f[i][j],ans%=MD;
printf("%d",ans);
return 0;
}