博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ1879】【SDOI2009】Bill的挑战 [状压DP]
阅读量:6293 次
发布时间:2019-06-22

本文共 1907 字,大约阅读时间需要 6 分钟。

Bill的挑战

Time Limit: 4 Sec  Memory Limit: 64 MB
[][][]

Description

 

  

Input

  第一行:一个整数T,表示数据的个数。 
  对于每组数据: 
    第一行:两个整数,N和K(含义如题目表述)。 
    接下来N行:每行一个字符串。

Output

  T行,每行一个整数表示答案

Sample Input

  1

  2 1
  a?
  ?b

Sample Output

  50

HINT

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

Solution

  我们运用状压DP,令 g[i][c] 表示第 i 位,用 字符c匹配可行的串的集合

  然后显然就可以DP啦!f[i][opt] 表示做到了第 i 位匹配集合为opt的方案数。

Code

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 using namespace std; 10 typedef long long s64;11 12 const int ONE = 4e5 + 5;13 const int MOD = 1000003;14 15 int n, m, T;16 int g[52][52], f[52][32769];17 char s[25][52];18 int Ans;19 20 int get()21 {22 int res=1,Q=1;char c;23 while( (c=getchar())<48 || c>57 ) 24 if(c=='-')Q=-1; 25 res=c-48; 26 while( (c=getchar())>=48 && c<=57 )27 res=res*10+c-48; 28 return res*Q;29 }30 31 32 void Deal()33 {34 memset(g, 0, sizeof(g));35 memset(f, 0, sizeof(f));36 n = get(); m = get();37 for(int i = 1; i <= n; i++)38 scanf("%s", s[i] + 1);39 40 int len = strlen(s[1] + 1);41 for(int i = 1; i <= len; i++)42 for(int c = 1; c <= 26; c++)43 for(int j = 1; j <= n; j++)44 if(s[j][i] == '?' || s[j][i] == c + 'a' - 1)45 g[i][c] |= 1 << j - 1;46 47 int total = (1 << n) - 1;48 f[1][total] = 1;49 for(int i = 1; i <= len; i++)50 for(int opt = 0; opt <= total; opt++)51 if(f[i][opt])52 for(int c = 1; c <= 26; c++)53 (f[i + 1][opt & g[i][c]] += f[i][opt]) %= MOD;54 55 Ans = 0;56 for(int opt = 0; opt <= total; opt++)57 {58 int num = 0;59 for(int j = 1; j <= n; j++)60 if(opt & (1 << j - 1)) num++;61 if(num == m) Ans = (Ans + f[len + 1][opt]) % MOD;62 }63 64 printf("%d\n", Ans);65 }66 67 int main()68 {69 T = get();70 while(T--)71 Deal();72 }73
View Code

 

转载于:https://www.cnblogs.com/BearChild/p/7630075.html

你可能感兴趣的文章
将图片转成base64字符串并在JSP页面显示的Java代码
查看>>
js 面试题
查看>>
sqoop数据迁移(基于Hadoop和关系数据库服务器之间传送数据)
查看>>
腾讯云下安装 nodejs + 实现 Nginx 反向代理
查看>>
Javascript 中的 Array 操作
查看>>
java中包容易出现的错误及权限问题
查看>>
AngularJS之初级Route【一】(六)
查看>>
服务器硬件问题整理的一点总结
查看>>
SAP S/4HANA Cloud: Revolutionizing the Next Generation of Cloud ERP
查看>>
Mellanox公司计划利用系统芯片提升存储产品速度
查看>>
白帽子守护网络安全,高薪酬成大学生就业首选!
查看>>
ARM想将芯片装进人类大脑 降低能耗是一大挑战
查看>>
Oracle数据库的备份方法
查看>>
Selenium 自动登录考勤系统
查看>>
关于如何以编程的方式执行TestNG
查看>>
智能照明造福千家万户 家居智能不再是梦
查看>>
物联网如何跳出“看起来很美”?
查看>>
浅谈MySQL 数据库性能优化
查看>>
《UNIX/Linux 系统管理技术手册(第四版)》——1.10 其他的权威文档
查看>>
灵动空间 创享生活
查看>>