nyoj17 單調遞增最長子序列(DP)

單調遞增最長子序列

描述

求一個字符串的最長遞增子序列的長度
如：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