【bzoj1879】[Sdoi2009]Bill的挑战

2015.04.25 15:14 Sat | 3次阅读 | 旧日oi | 固定链接 | 源码

Description

Input

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

Output

1 2 1 a? ?b

Sample Input

50

Sample Output

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

题解

开始在想SB的搜索……好像写好了也能过的样子。后来发现数据范围好小,直接状压一下就好了……
dp[i][st]表示前i位匹配模式为st的方案数。
match[i][now]表示第i位字符为now或?的字符串的集合,貌似有点ac自动机dp的感觉?

我的程序

#include <bits/stdc++.h>
using namespace std;
#define mod 1000003
int T,n,k,dp[55][1<<15],match[55][27],ans;
char s[20][55];
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&k);ans=0;
        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
        int len=strlen(s[1]+1);
        memset(dp,0,sizeof(dp));
        dp[1][(1<<n)-1]=1;
        for (int i=1;i<=len;i++)
        for(int now=0;now<26;now++)
        {
            match[i][now]=0;
            for(int k=1,kk=1;k<=n;k++,kk<<=1)
            if(s[k][i]=='?'||s[k][i]-'a'==now) match[i][now]|=kk;
        }
        for(int i=1;i<=len;i++)
        for(int j=0;j<(1<<n);j++)
        if(dp[i][j])
            for(int now=0;now<26;now++)
            dp[i+1][j&match[i][now]]=(dp[i+1][j&match[i][now]]+dp[i][j])%mod;
        for(int i=0;i<(1<<n);i++)
        {
            int cnt=0;
            for(int j=1;j<(1<<n);j<<=1) if(i&j) cnt++;
            if(cnt==k) ans=(ans+dp[len+1][i])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;       
}```