codeforces 1129C Morse Code[DP+trie]

题目链接

题目大意

用1、2、3、4 位二进制数表示26个英文字母。其中0011,0101,1110,1111这四种是没有对应的英语字母的，现在给你一个01串，求出01串的每一个前缀包含多少种英文字母的排列组合

例如 111
1表示 T
11 表示 M
111 表示 O

那么一串字符串 111 包含
“T” (translates into “1”)
“M” (translates into “11”)
“O” (translates into “111”)
“TT” (translates into “11”)
“TM” (translates into “111”)
“MT” (translates into “111”)
“TTT” (translates into “111”)

题目分析

首先，由于数据范围只有3000，所以，对于每次新添加一个字符，我们要求出，这一步会新增加多少个不同的英文字母。 考虑到能够组成英文字母的只有四个字符组成的串，那么我们只需要枚举最后四个字符，统计以每个字符开始，能够组成英文串的个数。
这里就用到一个dp的递推 dp[i] = dp[i+1] +…+dp[i+k] k表示的是最大长度，也就是说，以i开头的字符串，选取若干个合并，后面的就是一个子问题。（类似一个区间dp，但长度最大为4）
但是，我们求出英文串的个数，并不能直接加到原答案上去，因为要去重，所以，我们考虑在求解的时候建立一棵字典树，对于每一个串，我们都判断一下之前有没有出现过，如果没出现过，那么就是我们需要计算的新的答案了。

代码

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int maxn=5000;
int a[maxn];
ll f[maxn];
int n;
int v;
int tree[maxn*maxn][2];
int cv=2;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        v=1;
        for(int j=i-1;j>=0;j--)
        {
            int g = min(4,i-j);
            if(g==4)
            {
                int q = a[j]*8+a[j+1]*4+a[j+2]*2+a[j+3];
                if(q==3||q==5||q==14||q==15)g--;
            }
            f[j]=0;
            for(int k=1;k<=g;k++)
            {
                f[j]+=f[j+k];
            }
            f[j]%=mod;
            if(!tree[v][a[j]])
            {
                ans = (ans+f[j])%mod;
                tree[v][a[j]] = cv++;
            }
            v = tree[v][a[j]];
        }
        cout<<ans<<endl;

    }
    return 0;
}