【字母树+贪心】【HDU3460】【Ancient Printer】

时间:2023-03-09 00:59:54
【字母树+贪心】【HDU3460】【Ancient Printer】

题目大意:

一个打印机 只有 打印,删除,a-z。操作

给你一堆队名,如何才能操作次数最少输出全部

(字典树节点数-1)*2        输入,删除操作数
字符串数                 printf操作数

最长字符串的长度          最后一个不需要删除,所以尽量找最大的

所以

answer=(字典树节点数-1)*2+字符串数-最长字符串的长度
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
const int maxn=600000;
int T[maxn][26];
int A[maxn];
char buffer[55];
int tot=2;
int n;
int ans=0;
int MAX;
int TOT=0;
void CreatTrie(char *s)
{
int root=1;
for(int i=0;s[i];i++)
{
int p=s[i]-'a';
if(T[root][p]==0) T[root][p]=tot++;
root=T[root][p];
}
A[root]++;
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
void MEMSET()
{
MAX=-1;
tot=2;
ans=0;
TOT=0;
memset(A,0,sizeof(A));
memset(T,0,sizeof(T));
}
int dfs(int u)
{
ans++;
for(int i=0;i<26;i++)
{
if(T[u][i]!=0)
dfs(T[u][i]);
}
return 0;
}
int main()
{
// init();
while(cin>>n)
{
MEMSET();
for(int i=1;i<=n;i++)
{
scanf("%s",buffer);
int len=strlen(buffer);
if(len>MAX) MAX=len;
CreatTrie(buffer);
}
dfs(1);
printf("%d\n",(ans-1)*2+n-MAX);
}
return 0;
}