题解：SP24999 SMILEY1807 - 1807

· · 题解

翻译

在 smileyland 天使之国 SmileyLand。天使女王 Smiley1807 非常喜欢数字 1807 ，因此她要求她的程序员的朋友写一个程序来找到最大的子序列的长度，其顺序是数字 1 ， 8 ， 0 和 7 。例如，如果给定的序列是1800777700008888800077，那么满足上述条件的最大子序列之一是 1800000000777（或者 1888888000777），因此最大子序列的长度是 13 。
输入输出格式
输入格式：
输入只包含一个测试用例。测试用例只有一行，最长可达 10^6 。在输入序列中仅存在数字 1 ， 8 ， 0 和 7 。
输出格式：
输出只包含一行，包含最大子序列。

思路

开个数组，存数字 1 ， 8 ， 0 和 7 的先后顺序，然后……就是一个标准的最长不下降子序列问题了。
这个最长不下降子序列怎么做呢？
讲一个不一样的思路。
我们建一个数组存每种数的最后一个，这样就可以知道末尾为每种数的最长不下降子序列长度。每扫到一个数，到这个位置的最长不下降子序列长度就是末尾为应该在它之前出现数的最长不下降子序列长度加 1 和末尾为这个数的最长不下降子序列长度加 1 的最大值。

代码：

#include <bits/stdc++.h>
using namespace std;
int q[8],f[10000],z[8];
int main() {
    string xx;
    int x;
    cin>>xx;
    q[1]=1;q[8]=2;q[0]=3;q[7]=4;//先后顺序
    for(int i=0;i<=xx.size()-1;i++){
        x=q[xx[i]-'0'];
        f[i]=max(f[z[x]]+1,f[z[x-1]]+1);
        z[x]=i;
    }
    cout<<f[z[4]];
}