NKOJ 3824 解密游戏（trie，dp）

发表于 |
字数统计: 858字 | 阅读时长 ≈ 4min

P3824解密游戏

问题描述

小南和小开特别喜欢玩解密游戏，轮到小南加密的时候，由于他的加密方式过于丧心病 狂，所以小开怎么也不能解密成功，于是她来找你帮忙。 密文是一个长度为 n 的数字串，只由 0~9 之间的数字组成。每个小写字母对应 0~9 之 间的一个数字。小南和小开共同拥有一本字典，字典中有 m 个单词，每个单词长度不超过 50。 明文是一个数字，表示最少用多少个单词首尾拼接在一起，使得拼接而成的这个字符串 可以表示密文（也即相同位置的字符串中字母对应数字跟密文相同）。单词可以重复使用。
输出明文，如果无解的话明文为-1。

输入格式

第一行两个正整数 n,m。
第二行有 26 个数字，每个数字是 0~9 之间的数，分别表示字母 a~z 对应的数字。
第三行是长度为 n 的数字串，表示密文。 接下来 m 行，每行一个小写字母串，表示字典中的一个单词。

输出格式

输出一个整数，表示明文

样例输入 1

10 5 
2 2 2 3 3 3 4 4 1 1 5 5 6 6 0 7 0 7 7 8 8 8 9 9 9 0 7325189087 
it 
your 
reality 
real 
our

样例输出 1

2

样例输入 2

10 5 
2 2 2 3 3 3 4 4 1 1 5 5 6 6 0 7 0 7 7 8 8 8 9 9 9 0 4294967296 
it 
your 
reality 
real 
our

样例输出 2

-1

提示

【数据范围】
对于 30%的数据：1 ≤ n,m ≤ 1000。
对于 100%的数据：1 ≤ n,m ≤ 105。  
【样例 1 解释】
我们最少可以用两个单词 reality our，组成的字符串 realityour 去表示密文。  
【样例 2 解释】
没有选法使得单词组成的字符串可以表示密文。

此题显然需要进行字符串的匹配，KMP显然要超时，于是考虑trie。
对单词建立trie树后，把原串拿来匹配，套一个DP。
$F[j]=min(F[j],F[i-1]+1)，i和j是一个单词的起点和终点$
把原串的每一个位置都当做起点匹配一次，然后输出$F[length]$即可。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace  std;
struct node{int son[10],v;}trie[5000005];
int n,m,Q[233],LA,LB[100005],F[100005],tot=1;
char A[100005],B[100005][55];
void Ins(int x)
{
	int i,t,p=1;
	for(i=1;i<=LB[x];i++)
	{
		t=B[x][i]-48;
		if(!trie[p].son[t])trie[p].son[t]=++tot;
		p=trie[p].son[t];
	}
	trie[p].v=1;
}
void Fin(int x)
{
	int i,t,p=1;
	for(i=x;i<=LA;i++)
	{
		t=A[i]-48;
		if(!trie[p].son[t])break;
		p=trie[p].son[t];
		if(trie[p].v)F[i]=min(F[i],F[x-1]+1);
	}
}
int main()
{
	int i,j,k;char t;
	scanf("%d%d",&n,&m);
	for(i='a';i<='z';i++)scanf("%d",&Q[i]);
	scanf("%s",&A[1]);LA=strlen(A+1);
	for(i=1;i<=m;i++)
	{
		t=getchar();
		while(t<'a'||t>'z')t=getchar();
		for(k=0;t>='a'&&t<='z';t=getchar())B[i][++k]=Q[t]+48;
		LB[i]=k;Ins(i);
	}
	memset(F,60,sizeof(F));k=F[0];F[0]=0;
	for(i=1;i<=LA;i++)Fin(i);
	if(F[LA]==k)printf("-1");
	else printf("%d",F[LA]);
}