每日编程-20170401

题目：XXXX年突然有外星人造访，但大家语言不通，不过科学家们经过研究发现外星人用26个英文字母组成的单词中最长不降子序列的长度来表述数字，且英文字母的排列顺序不同，现给出其排列顺序，再给出外星人说的每个数字（其实是每个英文单词，用空格隔开），翻译出外星人所说的数字（连续输出，最后加回车）。 (因为是最长不降子序列，所以数字中没有0，也就是说外星人的数字是> =1的数字)

例如

我们正常的字母排列顺序是abcdefg…….xyz，代表a< b< c< …..< x< y< z abcd efg hhh ihg四个字符串的最长不降子序列的长度分别为4 3 3 1

输入格式：

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

输出格式：

输出答案 含义如题描述

1< =第二行长度< =255

样例输入

abcdefghijklmnopqrstuvwxyz
abcd efg hhh ihg
样例输出

4331

解答：

对于输入的字幕顺序，保存为字典，第一个字母对应0，最后一个对应25

将第二行的每个单词都用字典翻译一遍

接下来就是比数字大小

如果数组递增，tmp递增长度+1，直到递增停止，比最大递增长度与tmp递增长度

#include <iostream>
#include <sstream>
#include <map>
#include <vector>
using namespace std;
int Max(int a, int b) { return a < b ? b : a; }
int LongNotDown(vector<int> v) {
    int maxLong = 1,tmpNum = v[0], tmpLong = 1;
    for (auto i = 1; i < v.size(); i++)
    {
        if (v[i] >= tmpNum)
        {
            tmpNum = v[i];
            tmpLong++;
        }
        else
        {
            tmpNum = v[i];
            maxLong = Max(maxLong, tmpLong);
            tmpLong = 1;
        }
    }
    maxLong = Max(maxLong, tmpLong);
    return maxLong;
}
void getAlienNum(vector<vector<int>> v) {
    for (auto i = 0; i < v.size(); i++)
    {
        cout << LongNotDown(v[i]);
    }
    cout << endl;
}
int main() {
    string s;
    while (cin >> s)
    {    
        map<int, char> dic;
        for (auto i = 0; i < s.size(); i++)
        {
            dic[s[i]] = i;
        }
        string line,word;
        cin.ignore();
        getline(cin, line);
        istringstream words(line);
        vector<vector<int>> words2Num;
        vector<int> wordNum;
        while (words >> word)
        {
            for (auto i = 0; i < word.size(); i++)
            {
                wordNum.push_back(dic[word[i]]);
            }
            words2Num.push_back(wordNum);
            wordNum.clear();
        }
        getAlienNum(words2Num);
    }
}