nyoj17 单调递增最长子序列(DP)

?

• 题目17
• 题目信息
• 运行结果
• 本题排行
• 讨论区

  ?

  单调递增最长子序列

  时间限制：3000 ms | 内存限制：65535 KB 难度：4

  描述

  求一个字符串的最长递增子序列的长度
  如：dabdbf最长递增子序列就是abdf，长度为4

  输入

  第一行一个整数0 随后的n行，每行有一个字符串，该字符串的长度不会超过10000

  输出

  输出字符串的最长递增子序列的长度

  样例输入

  3
  aaa
  ababc
  abklmncdefg

  样例输出

  1
  3
  7

  来源

  经典题目

  上传者

  iphxer
  
  

  ?

  很简单的DP，从后往前慢慢推。。也很好理解

  记着几个经典的DP，以后的问题都是从这些简单的DP推出来的。。

  ?

   
  #include 
          
           
  #include 
           
             #include 
            
              using namespace std; int main() { char a[10001]; int t,len,i,j,dp[10001]; scanf(%d,&t); getchar(); while(t--) { gets(a); len=strlen(a); for(i=0;i
             
              =0;i--) { for(j=i+1;j
              
               
  ?
               
  ?