C++11(clang++ 3.9) 解法, 执行用时: 361ms, 内存消耗: 600K, 提交时间: 2020-08-24 20:16:09

#include <bits/stdc++.h>
using std::string;
using std::vector;
using std::map;
using std::min;

typedef string str;
const int N = 5500;
const int INF1 = 0x3f3f3f3f;
struct node{
	str s;
	int x;
	friend bool operator < (const node &lhs, const node &rhs) { 
		return lhs.s < rhs.s;
	} 
};
vector<node> v;
struct node1{
	int s, w;
};
node1 f[N][2];
map<str, int> dic;
int n;

int main(){
	//freopen("INPUT.008", "r", stdin);
	scanf("%d", &n);
	
	for (int i = 1; i <= n; ++i) { 
		node tmp;
		str s;
		
		std::cin >> s;
		
		if (s[0] == 'n') tmp.x = 1;
		if (s[0] == 'v') tmp.x = 2;
		if (s[0] == 'a') tmp.x = 4; 
		
		tmp.s="";
		for (int i = 2; i < s.length(); ++i) tmp.s += s[i];
		
		v.push_back(tmp);
	} 
	
	std::sort(v.begin(), v.end());
	
	node tmp;
	tmp.s = '$';
	v.push_back(tmp);
	
	int val = 0;
	for (int i = 0; i < v.size() - 1; ++i) { 
		val |= v[i].x;
		if (v[i].s != v[i + 1].s) { 
			dic.insert(std::pair<str, int>(v[i].s, val));
			val = 0;
		} 
	} 
	
	str text;
	std::cin >> text;
	text = "$" + text;
	int l = text.length();
	
	for (int i = 0; i < l - 1; ++i) 
		for (int j = 0; j < 2; ++j) f[i][j].s = f[i][j].w = INF1;
	f[0][0].s = f[0][0].w = 0;
	
	for (int i = 0; i < l - 2; ++i) { 
		for (int j = 0; j < 2; ++j) { 
			if (f[i][j].s == INF1) continue;
			
			str s = "";
			for (int k = i + 1; k < l - 1; ++k) { 
				s += text[k];
				auto it = dic.find(s);
				
				if (it == dic.end()) continue;
				
				if (it->second & 1) { 
					int z = j ? 0 : 1;
					
					if (f[k][0].s > f[i][j].s + z) { 
						f[k][0].s = f[i][j].s + z;
						f[k][0].w = f[i][j].w + 1;
					} 
					else if (f[k][0].s == f[i][j].s + z && f[k][0].w > f[i][j].w + 1)
						f[k][0].w = f[i][j].w + 1;
				} 
				if (it->second & 2 && i != 0 && j != 1) { 
					if (f[k][1].s > f[i][j].s) { 
						f[k][1].s = f[i][j].s;
						f[k][1].w = f[i][j].w + 1;
					} 
					else if (f[k][1].s == f[i][j].s && f[k][1].w > f[i][j].w + 1) 
						f[k][1].w = f[i][j].w + 1; 
				} 
				if (it->second & 4 && k != l - 2) { 
					if (f[k][j].s > f[i][j].s) { 
						f[k][j].s = f[i][j].s;
						f[k][j].w = f[i][j].w + 1;
					} 
					else if (f[k][j].s == f[i][j].s && f[k][j].w > f[i][j].w + 1) 
						f[k][j].w = f[i][j].w + 1; 
				} 
			} 
		} 
	} 
	
	
	if (f[l - 2][0].s < f[l - 2][1].s) 
		printf("%d\n%d\n", f[l - 2][0].s, f[l - 2][0].w);
	else if (f[l - 2][0].s > f[l - 2][1].s) 
		printf("%d\n%d\n", f[l - 2][1].s, f[l - 2][1].w);
	else printf("%d\n%d\n", f[l - 2][0].s, min(f[l - 2][0].w, f[l - 2][1].w));
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 1380K, 提交时间: 2020-08-24 17:49:27

#include<bits/stdc++.h>

#define ri register int

#define inf 0x3f3f3f3f

using std::min;
using std::max;
using std::pair;
using std::make_pair;

const int MAXN=1010;
const int MAXM=5010;

int n,m;

char buf[30];
char s[MAXM];

pair<int,int> f[MAXM][4];

//0:n.
//1:v.
//2:n. with a.
//3:v. with a.

struct trie
{
	int sz;
	struct node
	{
		int v,ch[26];
	}a[MAXN*20];
	void insert(char *s,int len,int v)
	{
		ri u=0,son;
		for(ri i=0;i<len;++i)
		{
			son=s[i]-'a';
			if(!a[u].ch[son])a[u].ch[son]=++sz;
			u=a[u].ch[son];
		}
		a[u].v|=v;
	}
	int find(char *s,int len)
	{
		ri u=0,son;
		for(ri i=0;i<len;++i)
		{
			son=s[i]-'a';
			if(!a[u].ch[son])return 0;
			u=a[u].ch[son];
		}
		return a[u].v;
	}
}tree;

int main()
{
//	freopen("in.in","r",stdin);
	
	scanf("%d",&n);
	for(ri i=1,v;i<=n;++i)
	{
		memset(buf,0,sizeof(buf));
		scanf("%s",buf+1);
		if(buf[1]=='n')v=1;
		else if(buf[1]=='v')v=2;
		else v=4;
		tree.insert(buf+3,strlen(buf+3),v);
	}
	
	scanf("%s",s+1);
	m=strlen(s+1)-1;
	for(ri i=0;i<=m;++i)
		for(ri j=0;j<4;++j)
			f[i][j]=make_pair(inf,inf);
	f[0][0]=make_pair(0,0);
	
	for(ri i=1,v;i<=m;++i)
	{
		for(ri j=i-1;j>=max(0,i-20);--j)
		{
			v=tree.find(s+j+1,i-j);
			pair<int,int> p0=min(f[j][0],f[j][2]),p1=min(f[j][1],f[j][3]);
			if(v&1)
			{
				f[i][0]=min(f[i][0],make_pair(p0.first+1,p0.second+1));
				f[i][0]=min(f[i][0],make_pair(p1.first  ,p1.second+1));
			}
			if(v&2 && j!=0)
			{
				f[i][1]=min(f[i][1],make_pair(p0.first  ,p0.second+1));
				f[i][1]=min(f[i][1],make_pair(inf       ,inf        ));
			}
			if(v&4)
			{
				f[i][2]=min(f[i][2],make_pair(p0.first  ,p0.second+1));
				f[i][3]=min(f[i][3],make_pair(p1.first  ,p1.second+1));
			}
		}
//		for(ri j=0;j<4;++j)
//			printf("f[%d][%d]=(%d,%d)\n",i,j,f[i][j].first,f[i][j].second);
	}
	
	pair<int,int> ans=min(f[m][0],f[m][1]);
	printf("%d\n%d\n",ans.first,ans.second);
	
	return 0;
}