DP，最長不下降子序列。
Here is my code:
#include<iostream>
#include<string>
#include<string.h>
#define maxn 307
using namespace std;
string rkey,s;
long f(char ch)
{
for(long i=0;i<26;i++)
if(rkey.at(i)==ch)
return i;
return 0;
}
int main()
{
cin>>rkey;
while(cin>>s)
{
long len=s.length(),ans,r[maxn],d[maxn];
for(long i=1;i<=len;i++)
r[i]=f(s.at(i-1));
for(long i=1;i<=len;i++)
d[i]=1;
for(long i=1;i<=len;i++)
for(long j=1;j<i;j++)
if(r[j]<=r[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
ans=0;
for(long i=1;i<=len;i++)
if(ans<d[i])
ans=d[i];
cout<<ans;
}
cout<<endl;
return 0;
}
posted on 2010-10-22 01:14
lee1r 閱讀(431)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃