当前位置:   article > 正文

[Codeforces 697F] Legen... (AC自动机+取max的矩阵快速幂)_有积里0a976f

有积里0a976f

Codeforces - 697F

构造一个长度为 l的串,其中每包含一个第 i个单词,能获得 ai的价值
单词可重复,也可相互覆盖,问最大价值是多少


一看就是AC自动机,但是 l特别大,有 1014,所以要用矩阵快速幂
但是这个dp过程是取max的,所以矩阵和一般的都不一样
由于运算符的抽象性,
所以可以把矩阵乘法中的整数的乘法,即加权的方式,视作加法
把整数的加法,即各个子状态转移的方式,视作取 max

然后相应的,原来的单位矩阵,对角线上是 1,其他是 0
1是乘法的幺元,0是乘法的零元,加法的幺元
1改成 0 ,0改成负无穷
0是加法的幺元,负无穷是加法的零元,取 max的幺元
然后用这样的定义重载矩阵乘法,构造矩阵,进行矩阵快速幂即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Sqr(a) ((a)*(a))

const int maxn=210;
const LL INF=0x3f3f3f3f3f3f3f3f;
struct Matrix
{
    LL n[maxn][maxn], siz;
    Matrix(int _siz=maxn){MST(n,-1); siz=_siz;}
    void E(){MST(n,-1); for(int i=0; i<siz; i++) n[i][i]=0;}
    Matrix operator * (const Matrix &v) const
    {
        Matrix tem(siz);
        for(int i=0; i<siz; i++) for(int j=0; j<siz; j++) for(int k=0; k<siz; k++)
            if(~n[i][k] && ~v.n[k][j]) tem.n[i][j] = max(tem.n[i][j], n[i][k]+v.n[k][j]);
        return tem;
    }
};

Matrix Pow(Matrix x, LL n)
{
    Matrix res;
    res.E();
    while(n)
    {
        if(n&1) res=x*res;
        x=x*x;
        n>>=1;
    }
    return res;
}

struct AC_Auto
{
    const static int nsiz=26;
    struct node
    {
        char chr;
        int fail, nxt[nsiz];
        LL val;
    } trie[maxn];
    int siz;
    int chnum(char a){return a-'a';}
    void init(){siz=0; CLR(trie);}
    void addstr(char*,int);
    void construct();
    LL solve(LL);
};


int N;
LL L;
int A[maxn];
char patn[maxn];
AC_Auto ac;

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    #endif

    ac.init();  
    scanf("%d%lld", &N, &L);
    for(int i=0; i<N; i++) scanf("%d", &A[i]);
    for(int i=0; i<N; i++)
    {
        scanf(" %s", patn);
        ac.addstr(patn,A[i]);
    }
    ac.construct();
    printf("%lld\n", ac.solve(L));
    return 0;
}

LL AC_Auto::solve(LL len)
{
    Matrix res(siz+1);
    for(int np=0; np<=siz; np++)
    {
        for(int i=0; i<nsiz; i++)
        {
            int nxp=trie[np].nxt[i];
            if(nxp) res.n[nxp][np] = max(res.n[nxp][np], (LL)trie[nxp].val);
        }
    }
    res = Pow(res,len);
    LL ans=0;
    for(int i=1; i<=siz; i++) ans=max(ans, res.n[i][0]);
    return ans;
}

void AC_Auto::addstr(char str[], int val)
{
    int np=0, len=strlen(str);
    for(int i=0; i<len; i++)
    {
        int chn=chnum(str[i]);
        if(trie[np].nxt[chn]) np=trie[np].nxt[chn];
        else
        {
            trie[np].nxt[chn]=++siz;
            np=siz;
            trie[np].chr=str[i];
        }
        if(i==len-1) trie[np].val+=val;
    }
}

void AC_Auto::construct()
{
    queue<int> que;
    for(int i=0; i<nsiz; i++)
    {
        int np=trie[0].nxt[i];
        if(np) que.push(np);
    }
    while(que.size())
    {
        int np=que.front(); que.pop();
        for(int i=0; i<nsiz; i++)
        {
            int nxp=trie[np].nxt[i];
            int fap=trie[np].fail;
            if(!nxp) trie[np].nxt[i]=trie[fap].nxt[i];
            else
            {
                que.push(nxp);
                trie[nxp].fail = trie[fap].nxt[i];
                fap = trie[nxp].fail;
                trie[nxp].val += trie[fap].val;
            }
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/710452
推荐阅读
相关标签
  

闽ICP备14008679号