首页 > 题解 > luogu 2167 [SDOI2009]Bill的挑战

luogu 2167 [SDOI2009]Bill的挑战

还是一道诡异的DP

地址:luogu2167

题目描述

输入输出格式

输入格式:

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

输出格式:

T行整数,表示结果

输入输出样例

输入样例#1:

1
2 1
a?
?b

输出样例#1:

50

数据范围

对于30%的数据,T ≤ 5,M ≤ 5,字符串长度≤ 20;

对于70%的数据,T ≤ 5,M ≤ 13,字符串长度≤ 30;

对于100%的数据,T ≤ 5,M ≤ 15,字符串长度≤ 50。

题解

一眼数据范围:你好状压

因为每个字符串都是相同长度的,我们可以先预处理一个$match[1 \cdots len][a \cdots z]$,里面用二进制表示¥1 \cdots n¥位的字符串的第¥i¥位是否可以匹配上¥a \cdots z¥。

然后转移就非常好想了,¥f[i][j]¥表示第i位的匹配上了j这个状态的方案数,然后随便瞎搞统计结果就行了。。。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×