9.25停课刷题P4460

· · 题解

本应该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;
}

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