Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给一个只由小写字母组成的字符串，每个字符映射到一个数字，问映射之后的最长上升子序列的长度。。
思路：上来写nlogn的LIS是我无脑了。。。wa了之后想了下。。其实只要统计不同的字母数就好了啊。。。set一下
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月14日 星期日 12时13分22秒
4File Name :code/ccpc2016/1011.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <deque>
20#include <ctime>
21#define fst first
22#define sec second
23#define lson l,m,rt<<1
24#define rson m+1,r,rt<<1|1
25#define ms(a,x) memset(a,x,sizeof(a))
26typedef long long LL;
27#define pi pair < int ,int >
28#define MP make_pair
29
30using namespace std;
31const double eps = 1E-8;
32const int dx4[4]={1,0,0,-1};
33const int dy4[4]={0,-1,1,0};
34const int inf = 0x3f3f3f3f;
35const int N=1E5+7;
36char s[N];
37int a[N];
38int dp[N];
39int g[N];
40set<int>se;
41int main()
42{
43 #ifndef ONLINE_JUDGE
44 freopen("code/in.txt","r",stdin);
45 #endif
46 int T;
47 int cas = 0 ;
48 cin>>T;
49 while (T--)
50 {
51 scanf("%s",s);
52 ms(a,0);
53 ms(dp,0);
54 ms(g,0x3f);
55 int len = strlen(s);
56 for ( int i = 0 ; i < len ; i++)
57 a[i+1] = s[i]-'a'+1;
58
59 int res = 0 ;
60 se.clear();
61 for ( int i = 1 ; i <= len ;i++) se.insert(a[i]);
62 res = se.size();
63
64 /* for ( int i = 1 ; i <= len ; i++)
65 {
66 // cout<<"i:"<<a[i]<<endl;
67 int k = lower_bound(g+1,g+len+1,a[i])-g;
68 dp[i] = k;
69 g[k] = a[i];
70 res = max(res,dp[i]);
71 } */
72 printf("Case #%d: %d\n",++cas,res);
73
74 }
75
76 #ifndef ONLINE_JUDGE
77 fclose(stdin);
78 #endif
79 return 0;
80}