1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <stdio.h>
#include <string.h>
int q(char *input,int begin,int end,char elem)
{
if(begin >= end) return end;
int mid = (begin+end)/2;
if(input[mid] < elem) return q(input,mid+1,end,elem);
else return q(input,begin,mid,elem);
}
int main(int argc, char const *argv[])
{
int t,top,l;
char input[10010],s[10010];
scanf("%d",&t);
while(t--)
{
scanf("%s",input);
top = 1;
s[0]=input[0];
for(int i = 1;i<strlen(input);++i)
{
if(s[top-1] < input[i]){
s[top++] = input[i];
}else{
l=q(s,0,top-1,input[i]);
s[l] = input[i];
}
}
printf("%d\n",top);
}
return 0;
}
|
