首页 > 其他 > 详细

洛谷P1481 魔族密码 简单DP

时间:2019-08-15 15:48:11      阅读:95      评论:0      收藏:0      [点我收藏+]

题目描述

风之子刚走进他的考场,就……

花花:当当当当~~偶是魅力女皇——花花!!^^(华丽出场,礼炮,鲜花)

风之子:我呕……(杀死人的眼神)快说题目!否则……-_-###

花花:……咦好冷我们现在要解决的是魔族的密码问题(自我陶醉:搞不好魔族里面还会有人用密码给我和菜虫写情书咧,哦活活,当然是给我的比较多拉*^_^*)。魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表,每个单词至少包含1个字母,至多75个字母。如果在一个由一个词或多个词组成的表中,除了最后一个以外,每个单词都被其后的一个单词所包含,即前一个单词是后一个单词的前缀,则称词表为一个词链。例如下面单词组成了一个词链:

i int integer

但下面的单词不组成词链:

integer

intern 现在你要做的就是在一个给定的单词表中取出一些词,组成最长的词链,就是包含单词数最多的词链。将它的单词数统计出来,就得到密码了。

风之子:密码就是最长词链所包括的单词数阿……

花花:活活活,还有,看你长得还不错,给你一个样例吧:

输入格式

这些文件的格式是,第一行为单词表中的单词数N(1<=N<=2000),下面每一行有一个单词,按字典顺序排列,中间也没有重复的单词咧!!

输出格式

你要提交的文件中只要在第一行输出密码就行啦^^

输入输出样例

输入

5
i
int
integer
intern
internet

输出

4

题解

简单DP题
方便起见我们不用数组,而用map来存dp状态
dp[s[i]]表示当前末尾单词为s[i]时的最大值
显然:dp[s[i]]=max(1,dp["s[i]的前缀"]+1)

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    register char c=getchar();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();
    return _*f;
}
int n;
string s[2005];
set<string> note[2005];
bool cmp(string a,string b){
    return a.size()<b.size();
}
map<string,int> dp;//以单词i结尾时的最大值 
signed main(){
    //freopen("1.txt","r",stdin);
    n=read();
    for(register int i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+1+n,cmp);
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<i;j++){
            if(s[i].find(s[j])==0)note[i].insert(s[j]);
        }
    }
    int ans=0;
    for(register int i=1;i<=n;i++){
        dp[s[i]]=1;
        for(register set<string>::iterator it=note[i].begin();it!=note[i].end();it++){
            dp[s[i]]=max(dp[s[i]],dp[*it]+1);
            ans=max(ans,dp[s[i]]);
        }
    }
    cout<<ans<<endl;
}

洛谷P1481 魔族密码 简单DP

原文:https://www.cnblogs.com/Chen574118090/p/11358215.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!