BZOJ1879:[SDOI2009]Bill的挑战(状压DP)-白红宇

BZOJ1879:[SDOI2009]Bill的挑战(状压DP)

阅读量：5822 次

发布时间：2019-06-18

本文共 1470 字，大约阅读时间需要 4 分钟。

Description

Input

本题包含多组数据。

第一行：一个整数T，表示数据的个数。

对于每组数据：

第一行：两个整数，N和K（含义如题目表述）。

接下来N行：每行一个字符串。

T ≤ 5，M ≤ 15，字符串长度≤ 50。

Output

如题

Sample Input

3 3

???r???

???????

3 4

???????

?????a?

???????

3 3

???????

?a??j??

????aa?

3 2

a??????

???????

3 2

???????

???a???

????a??

Sample Output

914852

871234

67018

Solution

第一眼数据范围：撞鸭状压DP没跑了

而且连压什么都告诉你了，毕竟只有N能压

状态设计很简单：f[i][S]该选第i列了，当前选中的行是集合S

然后我后面就G了……搞了半天又是容斥又是各种判断乱搞只有20……

其实预处理一下就非常好做了。

预处理出g[第i列][j字母]=集合x

表示j字母可以和集合x的第i位匹配(我第一次看的时候有点绕)

然后就枚举当为集合x的时候第i位填j字母然后进行转移就好了

果然我就是R1出题人说的"学数据结构学傻了"

虽然我数据结构仍然辣鸡

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #define MAXN (40001) 5 using namespace std; 6 int f[52][MAXN],g[52][31]; 7 int N,K,T,len,sum; 8 char s[101][101]; 9 10 int main()11 {12     scanf("%d",&T);13     while (T--)14     {15         memset(f,0,sizeof(f));16         memset(g,0,sizeof(g));17         scanf("%d%d",&N,&K);18         for (int i=1; i<=N; ++i)19             scanf("%s",s[i]+1);20         len=strlen(s[1]+1);21         22         for (int i=1; i<=len; ++i)23             for (int j=0; j<26; ++j)24                 for (int k=1; k<=N; ++k)25                     if (s[k][i]=='?' || s[k][i]==j+'a')26                         g[i][j]|=(1<
        
         >=1;44             }45             if (cnt==K) (ans+=f[len][i])%=1000003;46         }47         printf("%d\n",ans);48     }49 }