P1024-题解（C++代码）

解题思路:

子问题：以第i个为终点的最长不降子序列

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

    string rule;

    string str;

    cin>>rule;

    while(cin>>str)

    {

        int dp[50]; //以第i个为终点的最长不降子序列

        int L=str.length();

        for(int i=0;i<L;i++)

            dp[i]=1;

        for(int i=1;i<L;i++)

        for(int j=0;j<i;j++)

        {

            int n1,n2;

            for(int k=0;k<26;k++)

            {

                if(rule[k]==str[i])

                    n1=k;

                if(rule[k]==str[j])

                    n2=k;

            }

            if(n1>=n2)

                dp[i]=max(dp[i],dp[j]+1);

        }

        cout<<*max_element(dp,dp+L);

    }

    return 0;

}