Blackops

初心易得，始终难守

0%

ELOJ 014 War-cry（AC自动机+DP+滚动数组优化）

发表于 分类于 ， ，

War-cry
Time limit = 4

Chieftains of Mumba-Lumba decided make up new war-cry to increase martial spirit and to frighten enemy.
Alphabet B of Mumba-Lumba consists of M letters. War-cry should be word in this alphabet of length N. Scientists of Mumba-Lumba found out set of different elementary screams (words in the alphabet B) {s1 s2 … sk} which arouse fear in enemy equal to {f1 f2 … fk} correspondingly. Number fi is nonnegative integer less than 10000.

Each instance of word si in war-cry adds to its fearness number fi.

Number fi may not be equal to fierness of the word si, because si may contains one or more other elementary screams as subwords.

Input First line contains three numbers N, M and K delimited with space. K is the number of elementary screams. 1 ≤ N ≤ 100, 1 ≤ M ≤ 25, 1 < K ≤ 100. Next line contains Mubma-Lubma alphabet — different lowcase latin letters. Next lines contain information about elementary screams. Each line has format of

< word > < it’s fearness >

Output Maximum value of fearness among words of length N and example of word of length N with this fearness in the next line.

Input#1
4 3 4
abc
a 1
b 1
ab 3
caa 6
Output#1
12
caab

Input#2
7 10 4
abcdefghij
a 1
b 1
ab 4
bac 8
Output#2
25
bacabac

题目链接：ELOJ 014
不得不吐槽这神奇的评测网站，第一次见，而且注册的时候似乎还会默认把每一次的评测结果发送到你邮箱，然后在更改资料前我的邮箱就爆炸了……。提交了11发
这题初看显然就是个简单的AC自动机上的DP嘛……按套路建立的时候传递叠加fail指针的价值，然后估计是$dp[i][j]$表示构造长度为$i$的字符窜且此时在节点$j$上的最大值，由于合法性问题，$dp$数组要初始化为$-\infty$然后转移方程就是

嗯妥了妥了，然后发现这题空间不好估计啊，也没找到内存限制在哪里，然后就开始瞎搞，发现不是WA就是MLE……然后发现这转移方程不是显然可以用滚动数组优化的嘛XD，然后感觉WA的情况应该是一开始输入的字符集没映射好，当没用的数组扔掉了……先在前面映射一发就可以了。。
代码：

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
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200000;
struct Trie
{
    int nxt[26];
    int fail, v;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        fail = v = 0;
    }
} L[N];
int sz;
int n, m, k;
int dp[2][10010];
char dps[2][10010][105];
int vis[90], order['z' + 1], revmap[28];

namespace ac
{
    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    void ins(char s[], int len, int v)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
            if (order[(int)s[i]] == -1)
                return ;
        for (int i = 0; i < len; ++i)
        {
            int v = order[(int)s[i]];
            if (L[u].nxt[v] == -1)
            {
                L[sz].init();
                L[u].nxt[v] = sz++;
            }
            u = L[u].nxt[v];
        }
        L[u].v += v;
    }
    void build()
    {
        L[0].fail = 0;
        queue<int>Q;
        for (int i = 0; i < m; ++i)
        {
            int v = L[0].nxt[i];
            if (~v)
            {
                Q.push(v);
                L[v].fail = 0;
            }
            else
                L[0].nxt[i] = 0;
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            L[u].v += L[uf].v;
            for (int i = 0; i < m; ++i)
            {
                int v = L[u].nxt[i];
                if (~v)
                {
                    L[v].fail = L[uf].nxt[i];
                    Q.push(v);
                }
                else
                    L[u].nxt[i] = L[uf].nxt[i];
            }
        }
    }
}
int main(void)
{
    int i, j;
    char tt[30];
    while (~scanf("%d%d%d", &n, &m, &k))
    {
        ac::init();
        CLR(vis, 0);
        CLR(dp, -INF);
        CLR(dps, 0);
        scanf("%s", tt);
        sort(tt, tt + m);
        CLR(order, -1);
        for (i = 0; i < m; ++i)
        {
            order[(int)tt[i]] = i;
            revmap[i] = tt[i] - 'a';
        }
        for (i = 0; i < k; ++i)
        {
            int w;
            scanf("%s%d", tt, &w);
            ac::ins(tt, strlen(tt), w);
        }
        ac::build();
        int ans = 0;
        int cur = 0;
        int nxt = 1;
        dp[cur][0] = 0;
        char temp[105] = {0}, ans_str[105] = {0};
        for (i = 0; i < n; ++i)
        {
            CLR(dp[nxt], -INF);
            for (j = 0; j < sz; ++j)
            {
                if (dp[cur][j] < 0)
                    continue;
                for (int s = 0; s < m; ++s)
                {
                    int v = L[j].nxt[s];
                    int tv = dp[cur][j] + L[v].v;
                    strcpy(temp, dps[cur][j]);
                    temp[i] = 'a' + revmap[s];
                    temp[i + 1] = '\0';
                    if (tv > dp[nxt][v])
                    {
                        dp[nxt][v] = tv;
                        strcpy(dps[nxt][v], temp);
                    }
                }
            }
            swap(cur, nxt);
        }
        for (i = 0; i < sz; ++i)
        {
            if (dp[cur][i] > ans)
            {
                ans = dp[cur][i];
                strcpy(ans_str, dps[cur][i]);
            }
        }
        printf("%d\n%s\n", ans, ans_str);
    }
    return 0;
}