단조로운 증가 최장자 서열 (동적 기획)

4026 단어 동적 기획
단조 증가 최장자 서열
시간 제한:
3000ms | 메모리 제한: 65535KB
난이도:
4
묘사
문자열의 가장 긴 증자 서열의 길이를 구하다
예를 들어 dabdbf의 가장 긴 증자 서열은 abdf이고 길이는 4이다
입력
첫 번째 줄 <20개의 정수 0다음 n 행에는 각 행에 문자열이 있으며, 문자열의 길이는 10000을 초과하지 않습니다.
출력
출력 문자열의 최대 시퀀스 길이
샘플 입력
3
aaa
ababc
abklmncdefg

샘플 출력
1
3
7
 1 #include<stdio.h>
 2 #include<string.h>
 3 int main(){char s[10010],dp[10010],maxlen;
 4 int n;
 5     scanf("%d",&n);
 6     while(n--){
 7         memset(dp,0,sizeof(dp));
 8         scanf("%s",s);
 9         dp[0]=1;
10         maxlen=1;
11         for(int i=1;s[i];i++){dp[i]=1;
12             for(int j=0;j<i;j++){
13                 if(s[j]<s[i]){
14                     dp[i]=dp[j]+1>dp[i]?dp[j]+1:dp[i];
15                 }
16             }
17             maxlen=dp[i]>maxlen?dp[i]:maxlen;
18         }
19         printf("%d
",maxlen); 20 } 21 return 0; 22 }//camnbdef

좋은 웹페이지 즐겨찾기