Logu p4683 [ioi2008] type printer problem solving

Luogu P4683 [IOI2008] Type Printer Answer key

Topic link ：P4683 [IOI2008] Type Printer

The question ：

You need to use a mobile printer to print out $N$ Word . This portable printer is an old-fashioned printer , It requires you to put some small pieces of metal （ Each contains a letter ） Put it on the printer to form words . Then press these small pieces of metal onto a piece of paper to print out the word . This printer allows you to do the following ：

• At the end of the printer's current word （ The tail ） Add a letter ;
• Delete a letter at the end of the current word in the printer （ Delete the last letter of the current word of the printer ）. This operation is only allowed if the printer currently has at least one letter ;
• Print out the current word on the printer .
  The printer is initially empty , Or it doesn't contain any metal blocks with letters . At the end of printing , Some letters are allowed to remain in the printer . It also allows you to print words in any order .

Because each operation takes some time , So you need to reduce the total number of operations as much as possible （ Minimize the total number of operations ）.

You need to write a program , Given the... To be printed $N$ Word , Find the minimum number of operations required to print all words in any order , And output a sequence of such operations .

For all the data ,$1\le N\le 25000$.

Obviously it can be used trie To do it （trie On dfs）

Because the last output word does not need to be deleted

So we consider greedily outputting the longest word

The specific method is to mark the path of the longest word , Run something else first and run it last

Time complexity $O(n\Sigma )$

Code ：

#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;
}

Reprint please explain the source