nyoj 17データ構造は最長で、単調にサブシーケンスをインクリメントします.

最長男シーケンスを単調にインクリメント
時間制限:
3000 ms |  メモリ制限:
65535 KB
難易度:
4
説明
文字列の最大増分のサブシーケンスの長さを求めます.
例えば、dabdbfの一番長いインクリメントサブシーケンスはabdfで、長さは4です.
入力
最初の行の整数0その後のn行には、各行に1つの文字列があります.この文字列の長さは10000を超えません.
出力
出力文字列の最大値は、サブシーケンスの長さを増加させます.
サンプル入力

3
aaa
ababc
abklmncdefg

サンプル出力

1
3
7

分析:
古典的なDPは、前から後ろに判断して、現在の増分長さを探し出します.後ろにあるのは前の大きさがないかもしれませんので、左の後が一番大きいとは限りません.01.#include<stdio.h>02.#include<string.h>03.int  main()04.{05.int  n;06.scanf("%d"・,&n);07.getchar();08.while(n--)09.{10.int  dp[10001];11.char  s[10001];12.int  max=1,l,i,j;13.gets(s);14.l=strlen(s);15.for(i=0;i<l;i++)16.dp[i]=1;17.for(i=1; i<l; i++)18.for(j=0; j<i; j++)19.if(s[i]>s[j]&&dp[i]<dp[j]+1)20.dp[i]=dp[j]+1;21.max=dp[0];22.for(i=0; i<l; i++)23.if(max<dp[i])24.max=dp[i];25.printf("
%d
"・,max);26.}27.return  0;28.}