洛谷P4683 [IOI2008] Type Printer 题解

题目链接：P4683 [IOI2008] Type Printer

题意：

你需要利用一台可移动的打印机打印出$N$个单词。这种可移动式打印机是一种老式打印机，它需要你将一些小的金属块（每个包含一个字母）放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作：

• 在打印机当前词的末端（尾部）添加一个字母；
• 在打印机当前词的尾部删去一个字母（将打印机当前词的最后一个字母删去）。仅当打印机当前至少有一个字母时才允许进行该操作；
• 将打印机上的当前词打印出来。
  初始时打印机为空，或者说它不含任何带字母的金属块。打印结束时，允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。

由于每一个操作都需要一定时间，所以需要你尽可能减少所需操作的总数目（将操作的总数最小化）。

你需要编写一个程序，给定所要打印的$N$个单词，找出以任意次序打印所有单词所需操作的最小数目，并输出一种这样的操作序列。

对于所有数据，$1\le N\le 25000$。

显然可以用trie来做（trie上dfs）

因为最后一个输出的单词不用删除

所以我们考虑贪心地把最长的单词最后输出

具体的做法就是把这个最长单词的路径标记，先跑别的最后跑它

时间复杂度 $O(n\Sigma )$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2.5e4+15)

string s[N];
signed trie[N*26][26];
int n,tot,c,mxlen,ed[N*26],ck[N*26];
void insert(int l,int id)
{
    int u=0;
    for(int i=0; i<l; i++)
    {
        int c=s[id][i]-'a';
        if(!trie[u][c])trie[u][c]=++tot;
        u=trie[u][c];
    }
    ed[u]=id;
}
void proc(int l,int id)
{
    int u=0;
    for(int i=0; i<l; i++)
    {
        int c=s[id][i]-'a';
        ck[trie[u][c]]=1;
        u=trie[u][c];
    }
}
int num;
string str;
void dfs(int u)
{
    if(ed[u])
    {
        ++num;
        str+="P";
    }
    if(num==n)
    {
        cout << str.size() << '\n';
        for(auto i : str)
            cout << i << '\n';
        exit(0);
    }
    for(int i=0; i<26; i++)
    {
        if(trie[u][i]&&!ck[trie[u][i]])
        {
            str+=char(i+'a');
            dfs(trie[u][i]);
            str+="-";
        }
    }
    for(int i=0; i<26; i++)
    {
        if(trie[u][i]&&ck[trie[u][i]])
        {
            str+=char(i+'a');
            dfs(trie[u][i]);
            str+="-";
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,l; i<=n; i++)
    {
        cin >> s[i];
        if(s[i].size()>mxlen)
        {
            mxlen=s[i].size();
            c=i;
        }
    }
    for(int i=1; i<=n; i++)
    {
        insert(s[i].size(),i);
        if(c==i) proc(s[i].size(),i);
    }
    dfs(0);
    return 0;
}
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

转载请说明出处