// Accept
//记忆式搜索
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char a[10002];
int b[10002];
int n,ans;
int f(int x)
{
int i,t;
if(b[x]>0) return b[x];
b[x]=1;
for(i=0;i<=x-1;i++)
{
t=f(i);
if(a[i]<a[x] && b[x]<t+1) b[x]=t+1;
}
return b[x];
}
int main( )
{
int i,j,len;
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%s",a);
len=strlen(a) ;
for(j=0;j<len;j++) b[j]=-1; // 设置一个不可能出现的结果
f(len-1);
ans=1;
for(j=0;j<len;j++)
if(ans<b[j]) ans=b[j];
cout<<ans<<endl ;
}
}
// DP
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char a[10002];
int b[10002];
int n,ans;
int dp(int x)
{
int i,j,max;
b[0]=1;
for(i=1;i<=x;i++)
{max=1;
for(j=0;j<i;j++)
if(a[j]<a[i] && max<b[j]+1) max=b[j]+1;
b[i]=max;
}
}
int main( )
{
int i,j,len;
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%s",a);
len=strlen(a) ;
dp(len-1);
ans=1;
for(j=0;j<len;j++)
if(ans<b[j]) ans=b[j];
cout<<ans<<endl ;
}
}
******************************************************************88
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char a[10002];
int b[10002];
int n,ans;
int dp(int x)
{
int i,j,max;
ans=b[0]=1;
for(i=1;i<=x;i++)
{max=1;
for(j=0;j<i;j++)
if(a[j]<a[i] && max<b[j]+1) max=b[j]+1;
b[i]=max;
if(b[i]>ans) ans=b[i];
}
}
int main( )
{
int i,j,len;
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%s",a);
len=strlen(a) ;
dp(len-1);
cout<<ans<<endl ;
}
}
poj 1088滑雪 //DP
#include <iostream>
using namespace std;
int a[102][102],b[102][102];
int r, c,ans;
int f( int i, int j )
{ int max=1,t;
if( b[i][j] > 1 ) return b[i][j];
if( i + 1 <= r && a[i][j] > a[i+1][j] )
{ t = f( i + 1, j ) + 1;
if( max < t ) max = t;
}
if( j + 1 <= c && a[i][j] > a[i][j+1] )
{ t = f( i, j + 1 ) + 1;
if( max < t ) max = t;
}
if( i - 1 > 0 && a[i][j] > a[i-1][j] )
{ t = f( i - 1, j ) + 1;
if( max < t ) max = t;
}
if( j - 1 > 0 && a[i][j] > a[i][j-1] )
{ t = f( i, j - 1 ) + 1;
if( max < t) max = t;
}
return max;
}
int main()
{ int i,j;
cin >> r >> c;
for ( i = 1; i <= r; ++i )
for ( j = 1; j <= c; ++j )
{ cin >> a[i][j]; b[i][j] = 1; }
ans = 1;
for( i = 1; i <= r; ++i )
for( j = 1; j <= c; ++j )
{ b[i][j] = f( i, j );
if( ans < b[i][j] ) ans = b[i][j];
}
cout << ans <<endl;
}
//2084 hdu c++ 数塔
#include <iostream>
#include<string.h>
using namespace std;
int a[105][105],b[105][105];
int n;
int max(int x, int y)
{ return x>y?x:y ; }
int f(int i,int j)
{
if(b[i][j]!=-1) return b[i][j];
return b[i][j]=a[i][j]+max(f(i+1,j),f(i+1,j+1));
}
int main()
{
int i,j,c;
cin>>c;
while(c--)
{
cin>>n ;
for(i=0;i<n;i++)
for(j=0;j<=i;j++) cin>>a[i][j];
memset(b,-1,sizeof(b));
for(j=0;j<n;j++) b[i-1][j]=a[i-1][j];
cout<<f(0,0)<<endl;
}
}