题意描述

[IOI2008] Type Printer 打印机

几百年前的 IOI 的题目还是很好的呀。

给你一个 诡异的 打印机，它只能用已有的字符来打印，而且必须每一个都用到。（这岂不是活字印刷术）

你可以对其执行三个操作：

1. 打印，用大写字母 P 表示，输出顺序任意，但仅能且必须用到当前打印机里的每一个字符。
2. 插入，输入一个字符 c，表示在打印机中插入字符 c。（打印机的存储是一个队列）
3. 删除，从队列尾部删除一个字符。

给定 \(N\) 个字符串，问当前需要至少多少步才能完成所有打印。

算法分析

考虑可爱的 \(trie\) 树，先建一棵树，假设当前已经建好了。（如果不会 你做这道题干什么 可以看看）

然后我们发现题目变成了：确定一个 \(DFS\) 的顺序，使得树上的每一个点都遍历到，并且结束于某个叶节点。

思想一

显然，倘若要求回到根节点，步数永远为 \(2\times (N-1)\)。（每条边都经过两次）

但是最后一条路径可以不回去，假设最后打印的字符串长度为 \(len\)，显然最终遍历步数为 \(2\times (N-1)-len\)。

注意：这里的遍历步数 \(\neq\) 答案步数，因为答案中还有删除操作。

显然 \(ans_{min}=2\times (N-1)-len_{max}\)。

思想二

既然每一个单词都要输出，打印的操作次数一定 = 总字符串数。

那么关键就是插入与删除次数尽量少，那么显然倘若要求删除次数尽量少，之前插入的字符长度应当尽量小。

所以最长的单词当然要最后打印。

当然以上的证明是不严谨的，但是有助于大家理解。

所以通过两种方法都可以确定贪心策略：最后走最长的单词，其他随意。

代码实现

其实还挺简单的。

1. 建树。不用讲解吧。
2. 标记。标记一下最长的字符串，也很简单。
3. dfs。最重要的环节了。在 dfs 时主要有三种操作：打印，向下遍历，回溯。

在打印时通过判断当前是否为单词的尾部来进行判断。

向下遍历时特殊处理被标记的节点。

回溯时倘若该点不是被标记的点，就打印 "-"。

看不懂的话看代码吧：

#include
#include
#include
#include
#include
#include
#define N 500010//几次空间开小了都 RE，所以索性开大一点，dalao 勿喷。
using namespace std;

int n,trie[N][30],tot=1;
bool sum[N],flag[N],finish=false;
//上面三个分别用来标记：是否是单词结尾（trie 基本操作），是否是最长字符串上的点，是否到了最后一个单词。
string a,jl,ans;

void insert(string a){
	int p=1;
	for(int i=0;i> a;insert(a);
		if(jl.length()