nyoj--16--單調遞增最長子序列

單調遞增最長子序列

時間限制： 3000 ms  |  記憶體限制： 65535 KB 難度： 4

描述

求一個字元串的最長遞增子序列的長度

如：dabdbf最長遞增子序列就是abdf，長度為4

輸入

第一行一個整數0<n<20,表示有n個字元串要處理

随後的n行，每行有一個字元串，該字元串的長度不會超過10000

輸出

輸出字元串的最長遞增子序列的長度

樣例輸入

3
aaa
ababc
abklmncdefg      

樣例輸出

1
3
7      

思路：

動态規劃的思想，把原問題分拆成若幹相對簡單的子問題，然後将其記憶化存儲，以便下次需要同一個子問題解決的時候直接查表。針對這一題，假如要求的字元串長度為l，就先求出前1,2,3,4，. . .  個字元串的解，把他們結果存儲在dp數組裡面，以便後面用到的時候直接查表，當程式運作到第l個時，問題也就解決了。

代碼：

 Java Code 

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 39 40 41 42

#include <iostream> #include<bits/stdc++.h> using namespace std; int  main() {     int  n;     int  dp[ 10005 ];     char  a[ 10005 ];    scanf( "%d" ,&n);     while (n--)    {        scanf( "%s" ,a);         int  l=strlen(a);         int  MAX=- 1 ;         for ( int  i= 0 ;i<l;i++)        {             ///求出前i個字元的結果            dp[i]= 1 ;             for ( int  j= 0 ;j<i;j++)            {                 ///查表計算                 if (a[j]<a[i]&&dp[i]<dp[j]+ 1 )                {                    dp[i]=dp[j]+ 1 ;                }            }        }         for ( int  i= 0 ;i<l;i++)        {             if (dp[i]>MAX)            {                MAX=dp[i];            }        }        printf( "%d\n" ,MAX);    }      return   0 ; }