Time Limit: 2000/1000 MS(Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 4367 Accepted Submission(s): 1265
Problem Description
Lweb has a string S. Oneday, he decided to transform this string to a new sequence. You need help him determine this transformation to get a sequence which has thelongest LIS(Strictly Increasing). You need transform every letter in this string to a new number. A is the set of letters of S, B is the setof natural numbers. Every injection f:A→B can be treatas an legal transformation. For example, a String “aabc”, A={a,b,c}, and you can transform it to “1 1 2 3”, and the LIS ofthe new sequence is 3. Now help Lweb, find the longest LIS which you can obtain from S. LIS: Longest Increasing Subsequence.(https://en.wikipedia.org/wiki/Longest_increasing_subsequence)
Input
The first line ofthe input contains the only integer T,(1≤T≤20). Then T lines follow, the i-th line contains a string S only containing the lowercase letters, the lengthof S will not exceed 105.
Output
For each testcase, output a single line "Case #x: y", where x is the case number,starting from 1. And y is the answer.
Sample Input
2
aabcc
acdeaa
Sample Output
Case #1: 3
Case #2: 4
题解：
这一题刚看的时候以为是求最长上升子序列，后来才发现排个序就判断就可以了。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100000+5; int a[N]; int d[N]; char s[N]; int main() { int t; int p; scanf("%d",&t); for(int j=0;j<t;j++) { memset(a,0,sizeof(a)); memset(d,0,sizeof(d)); memset(s,0,sizeof(s)); scanf("%s",s); //scanf("%d",&p); p=strlen(s); for(int i = 0; i < p; i++) { //scanf("%d",&a[i]); a[i]=s[i]; } sort(a,a+p); int len=1; for(int i=1;i<p;i++) { if(a[i]!=a[i-1]) { len++; } } printf("Case #%d: %d\n",j+1,len); } return 0; }
