CCPC网络赛，HDU_5842 Lweb and String

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 the longest 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 set of natural
numbers.

Every injection $f: A \rightarrow B$ can be treat as 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 of the 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 of the input contains the only integer
$T, (1 \leq T \leq 20)$.

Then $T$ lines follow, the i-th line contains a
string $S$ only containing the lowercase letters, the length of $S$ will not
exceed $10^5$.

Output

For each test case, output a single line "Case #x: y",
where x is the case number, starting from 1. And y is the answer.

Sample Input

aabcc

acdeaa

Sample Output

Case #1: 3

Case #2: 4

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include<cmath>

 using namespace std;

 char s[];

 int w[];

 int main()

 {

     int t;

     int d = ;

     int sum;

     scanf("%d",&t);

     while(t--)

     {

         sum = ;

         scanf("%s",&s);

         memset(w,,sizeof(w));

         for (int i=;i<strlen(s);i++)

         {

             if (w[s[i]-'a'] == ){

                 sum++;

                 w[s[i]-'a'] = ;

             }else

             continue;

         }

         printf("Case #%d: %d\n",++d,sum);

     }

     return ;

 }

思路解析：

这题就是题意的问题。A不出来都是被样例迷惑了！样例毁一生2333333，有时候理解真的比直接敲更有用。

巴特西

CCPC网络赛，HDU_5842 Lweb and String

最新文章

热门文章