bzoj5299: [Cqoi2018]解锁屏幕

题目链接

bzoj 5299: [Cqoi2018]解锁屏幕

题解

很水的装压dp，相信没人需要看题解....

dp[i][j]表示状态为i最后一个到的点为j,然后转移就很好写了

不过 我读入优化没读负数 ,为什么mod1e8 +7，我 mod 1e9 + 7 啊，WA了两发

#include<cstdio>

#include<vector>

#include<algorithm>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9'){if(c == '-')f = -1; c = getchar();}

    while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();

    return x * f;

}

#define mod 100000007

int n;

const int maxn = 21;

struct node {

    int x,y;

    bool operator < (const node &a)const {

        if(x == a.x) return y < a.y;

        return x < a.x;

    }

} loc[maxn];

int dp[(1 << maxn) + 7][maxn];

int po[maxn][maxn];

void get(node x,node y,int X,int Y) {

    int a = y.y - x.y , b = x.x - y.x , c = y.x * x.y - x.x * y.y;

        int tmp = 0;

    for(int i = X + 1;i < Y;++ i) {

        if(loc[i].x * a + loc[i].y * b + c == 0)

            tmp |= (1 << i);

            //if(i != Y)vec[X].push_back(i); if(i != X)vec[Y].pish_back(i);

    }

    po[X][Y] = tmp | (1 << X); // ^ (1 << Y);

    po[Y][X] = tmp | (1 << Y); // ^ (1 << X);

    //printf("%d\n",tmp);

}

int main() {

    n = read();

    for(int i = 0;i < n;++ i)

        loc[i].x = read(),loc[i].y = read();

    std::sort(loc,loc + n);

        for(int i = 0;i < n;++ i)

        for(int j = i + 1;j < n;++ j)

                get(loc[i],loc[j],i,j);

    int ans = 0;

    for(int i = 0;i < n;++ i) dp[1 << i][i] = 1;

    for(int i = 0;i < (1 << n);++ i) {

        //ans = 0;

        for(int j = 0;j < n;++ j) {

            if(((1 << j) & i)) continue;

            for(int k = 0;k < n;++ k) {

                if(!((1 << k) & i)) continue;

                if((po[k][j] & i) == po[k][j]){dp[i | (1 << j)][j] = (dp[i | (1 << j)][j] + dp[i][k]) % mod;}

            }

        }

    }

    for(int K,i = 0;i < (1 << n);++ i) {

        K = 0;

        for(int t = i;t;t >>= 1) if(t & 1)K ++;

        if(K >= 4) {

            for(int k = 0;k < n;++ k)

                ans = (ans + dp[i][k]) % mod;

        }

    }

    printf("%d\n",ans);

    return 0;

}