首页 > 代码库 > TYVJ 1024 外星人的密码数字 (DP)

TYVJ 1024 外星人的密码数字 (DP)

2024-08-04 15:31:30   209人阅读

P1024 外星人的密码数字
时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

    XXXX年突然有外星人造访，但大家语言不通，不过科学家们经过研究发现外星人用26个英文字母组成的单词中最长不降子序列的长度来表述数字，且英文字母的排列顺序不同，现给出其排列顺序，再给出外星人说的每个数字（其实是每个英文单词，用空格隔开），翻译出外星人所说的数字（连续输出，最后加回车）。
 (因为是最长不降子序列，所以数字中没有0，也就是说外星人的数字是>=1的数字)
例如
     我们正常的字母排列顺序是abcdefg…….xyz，代表a<b<c<…..<x<y<z
     abcd efg hhh ihg四个字符串的最长不降子序列的长度分别为4 3 3 1

输入格式

第1，2行为字符串
含义如题描述

输出格式

输出答案
含义如题描述

测试样例1

输入

abcdefghijklmnopqrstuvwxyz 
abcd efg hhh ihg

输出

4331

备注

1<=第二行长度<=255


该题被某人形容为恶心。。。。
其实也不是很难做吧？感谢！
zzy
 
水题
最长不下降子序列加一个预处理就行
#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<stack>#include<queue>#include<stdlib.h>#include<algorithm>using namespace std;const int MAXN=300+5;char dic[MAXN],str[MAXN],a[MAXN];int b[MAXN],dp[MAXN],cnt,lendic,lenstr,ans;int main(){    //freopen("in.txt","r",stdin);    scanf("%s",dic);    getchar();    gets(str);    cnt=0;    lenstr=strlen(str),lendic=strlen(dic);    for(int i=0;i<lendic;i++)        b[dic[i]-‘a‘]=i;    for(int i=0;i<=lenstr;i++)    {        if(str[i]==‘ ‘ || i==lenstr)        {            ans=0;            for(int j=0;j<cnt;j++)            {                dp[j]=1;                for(int k=0;k<j;k++)                {                    if(b[a[k]-‘a‘]<=b[a[j]-‘a‘])                        dp[j]=max(dp[j],dp[k]+1);                }                ans=max(ans,dp[j]);            }            printf("%d",ans);            memset(dp,0,sizeof(dp));            memset(a,0,sizeof(a));            cnt=0;        }        else a[cnt++]=str[i];    }    return 0;}
View Code

 

TYVJ 1024 外星人的密码数字 (DP)


联系
我们