[CQOI2018] 화면 잠금 해제

제목 설명:

자물쇠를 풀다.

제목 분석:

상압 DP야, 두 개의 점 링크에 필요한 필수 지점을 미리 처리한 다음에 DP는 만만해.

제목 링크:

BZOJ 5299 Luogu 4460

Ac 코드:

엄청난 속도 차이...DP 버전:

#include 
#include 
#include 
const int mod=100000007,maxm=21;
int ans=0;
int n;
int f[maxm][1<<20],a[maxm][maxm],x[maxm],y[maxm];
bool vis[maxm][1<<20];
inline bool atline(int d,int a,int b)
{
    if(x[d]<std::min(x[a],x[b])||x[d]>std::max(x[a],x[b])||y[d]<std::min(y[a],y[b])||y[d]>std::max(y[a],y[b])) return 0;
    return ((x[d]-x[a])*(y[b]-y[d])-(x[b]-x[d])*(y[d]-y[a])==0);
}
inline bool check(int sta)
{
    int cnt=0;
    for(int i=1;i<=n;i++) if((1<1))&sta) cnt++;
    return cnt>=4;
}
inline void add(int &a,int b)
{
    a+=b;
    if(a>=mod) a%=mod;
}
inline int read()
{
    int a=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
     a=(a<<3)+(a<<1)+ch-'0',ch=getchar();
    return a*w;
}
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=1;j<=n;j++)
      if(i!=j)
       for(int k=1;k<=n;k++)
        if(j!=k&&i!=k)
         if(atline(k,i,j)) a[i][j]|=(1<1));
    for(int i=1;i<=n;i++) f[i][1<1)]=1;
    for(int s=0;s1<int flag=check(s);
        for(int i=1;i<=n;i++)
        if(f[i][s])
        {
            if(flag) add(ans,f[i][s]);
            for(int j=1;j<=n;j++)
             if(!(s&(1<1))))
              if((s&a[i][j])==a[i][j])
               add(f[j][s|(1<1))],f[i][s]);
        }
    }
    printf("%d
",ans);
    return 0;
}

대기열 구현 버전:

#include 
#include 
#include 
const int mod=100000007,maxm=21;
int ans=0;
int n;
struct node{
    int last,sta,cnt;
};
int f[maxm][1<<20],a[maxm][maxm],x[maxm],y[maxm];
bool vis[maxm][1<<20];
std::queue  dl;
inline bool atline(int d,int a,int b)
{
    if(x[d]<std::min(x[a],x[b])||x[d]>std::max(x[a],x[b])||y[d]<std::min(y[a],y[b])||y[d]>std::max(y[a],y[b])) return 0;
    return ((x[d]-x[a])*(y[b]-y[d])-(x[b]-x[d])*(y[d]-y[a])==0);
}
inline void add(int &a,int b)
{
    a+=b;
    if(a>=mod) a%=mod;
}
inline int read()
{
    int a=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
     a=(a<<3)+(a<<1)+ch-'0',ch=getchar();
    return a*w;
}
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=1;j<=n;j++)
      if(i!=j)
       for(int k=1;k<=n;k++)
        if(j!=k&&i!=k)
         if(atline(k,i,j)) a[i][j]|=(1<1));
    for(int i=1;i<=n;i++) f[i][1<1)]=1,dl.push((node){i,1<1),1}),vis[i][1<1)]=1;
    while(!dl.empty())
    {
        node now=dl.front();
        dl.pop();
        if(now.cnt>=4) add(ans,f[now.last][now.sta]);
        for(int i=1;i<=n;i++)
        if(!((1<1))&now.sta))
        {
            if((now.sta&a[now.last][i])!=a[now.last][i]) continue;
            add(f[i][now.sta|(1<1))],f[now.last][now.sta]);
            if(!vis[i][now.sta|(1<1))]) dl.push((node){i,now.sta|(1<1)),now.cnt+1}),vis[i][now.sta|(1<1))]=1;;
        }
    }
    printf("%d
",ans);
    return 0;
}