JZOJ 3059. 雕塑

爱被打了一巴掌 2021-11-30 00:58 163阅读 0赞

# **题目** #

#### Description ####

【问题描述】

Wcyz为了迎接百年校庆，美化校园，请了校友笨笨将n座雕塑，准备安置在校园内，整个校园可以抽象成一个n\*n的大网格，每个1\*1网格最多只能安置一座雕塑，但是某些1\*1的网格上恰好是一个食堂或湖泊，这些网格是不能安置雕塑的，每个雕塑的造型相同，这样同一种安置方案中交换排列都算一种。任意雕塑在同一行或同一列是不合法的方案。

学校想知道有多少种安置方案，笨笨想从中选择最好的一种方案，笨笨想请你告诉他方

案种数。

#### Input ####

【输入格式】

第一行，两个整数n，m（n<=20,m<=10），用空格隔开，n表示n\*n的大网格，m表示不能安置雕塑的位置

第二行至m+1行，每行两个数x，y，用空格分开，表示坐标（x,y）的1\*1 的网格上不能安置雕塑。

#### Output ####

【输出格式】

一个数，方案种数（方案种数<=2^63-1）

#### Sample Input ####

6 7
    1 1
    2 1
    2 2
    3 3
    3 4
    4 3
    4 4

#### Sample Output ####

184

#### Data Constraint ####

#### Hint ####

n<=20,m<=10

# **分析** #

*  这道题真是让我笑死
 *  n=20，m=10 状压可能过不了哦
 *  算了试试吧
 *  结果拿了九十
 *  然后还错了一个点
 *  出题人有想啥，卡状压好吧我服了
 *  结果是WA，之前的大佬都是打标过的？？
 *  xswl
 *  设f\[i\]\[j\]为到当前第i行，前i-1行状态为j
 *  然后先把初始化1打出来
 *  方程为 f\[i\]\[j|(1<<k-1)\]+=f\[i-1\]\[j\];
 *  因为我们的状态是只有上一行影响所以可以开滚动数组
 *  x^=1;   \_\_builtin\_popcount(j)这东西能直接得到j在二进制下1的个数

# **代码** #

1 #include<iostream>
     2 using namespace std;
     3 int n,m;
     4 int map[30][30];
     5 long long f[2][1<<20+1];
     6 int a[21];
     7 int main ()
     8 {
     9     cin>>n>>m;
    10     for (int i=1,x,y;i<=m;i++) cin>>x>>y,map[x][y]=1;
    11     for (int i=1;i<=n;i++)
    12       for (int j=1;j<=n;j++)
    13         a[i]=(a[i]<<1)+map[i][j];
    14     int maxn=(1<<n)-1;
    15     int x=1; 
    16     for (int i=1;i<=n;i++) 
    17      if (!(a[1]&(1<<i-1))) 
    18       f[x][(1<<i-1)]=1;
    19     for (int i=2;i<=n;i++)
    20     {
    21         x^=1;
    22         for (int j=1;j<=maxn;j++)
    23         {
    24             if (__builtin_popcount(j)==i-1)
    25             {
    26                 for (int k=1;k<=n;k++)
    27                 {
    28                     if (!(j&(1<<k-1))&&!(a[i]&(1<<k-1)))
    29                       f[x][j|(1<<k-1)]+=f[x^1][j];
    30                 }
    31             }
    32         }
    33     }
    34     long long ans=0;
    35     for (int i=1;i<=maxn;i++)
    36       if (__builtin_popcount(i)==n)
    37           ans+=f[x][i];
    38     cout<<ans;
    39 }

转载于:https://www.cnblogs.com/zjzjzj/p/11178194.html