hdu 3460 Ancient Printer

浅浅的花香味﹌ 2021-12-16 19:15 154阅读 0赞

[http://acm.hdu.edu.cn/showproblem.php?pid=3460][http_acm.hdu.edu.cn_showproblem.php_pid_3460]

这题题意我就不想说了，做的真实气死我了。就是把给定数目的单词用他那个“ancient printer”给打印出来，让你把最少按键次数输出来。尼玛，

我最初的想法很简单，就是在ac自动机的基础上去，用深搜来跑。因为要求最少嘛，所以记得当时自己就一直在想怎么能满足最优，先打印存在前后缀长度短的，当时YY了好久，但是总是感觉不行。后来实在没办法才去google的，发现他们的方法特别。。，其实我当时也想到了，但是偏执的想跑一下深搜，结果自己还玩大了。按键次数=单词个数（因为要按print键）+2\*总共结点个数（ans）-最长字符串长度（ma）。最长放在最后打印，而且打印完之后可以允许字符依旧存在于打印机之中，不必退格删掉，所以要减去。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <algorithm>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    const int maxn=26;
    
    struct node
    {
        node *next[maxn];
        node()
        {
            for(int i=0;i<maxn;i++)
            {
                if(next[i]==NULL) continue;
                next[i]=NULL;
            }
        }
        ~node()
        {
            for(int i=0;i<maxn;i++)
            {
                if(next[i]!=NULL)
                    next[i]=NULL;
            }
        }
    };
    
    inline int max(int a,int b)
    {
        return a<b?b:a;
    }
    
    int ma,ans,n;
    class Trie
    {
        public:
        node *root;
        Trie()
        {
            root=NULL;
        }
        void insert(char *s)
        {
            if(!root)
                root=new node();
            int len=strlen(s);
            ma=max(ma,len);
            node *loca=root;
            for(int i=0;i<len;i++)
            {
                int id=s[i]-'a';
                if(loca->next[id]==NULL)
                {
                    ans++;
                    loca->next[id]=new node();
                }
                loca=loca->next[id];
            }
        }
    };
    
    int main()
    {
        char s[55];
        while(~scanf("%d",&n))
        {
            Trie t;
            ans=ma=0;
            for(int i=0;i<n;i++)
            {
                scanf("%s",s);
                t.insert(s);
            }
            printf("%d\n",n+2*ans-ma);
        }
        return 0;
    }

善待每一天，努力做好自己。

欢迎转载，注明出处。

转载于:https://www.cnblogs.com/RainingDays/archive/2013/05/09/3068524.html

[http_acm.hdu.edu.cn_showproblem.php_pid_3460]: http://acm.hdu.edu.cn/showproblem.php?pid=3460
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211216/8b0a4e8962104a41b1fd576137be7ac0.png