动态规划专题（一） HDU1087 最长公共子序列

Super Jumping! Jumping! Jumping!

首先对于动态规划问题要找出其子问题，如果找的子问题是前n个序列的最长上升子序列，但这样的子问题不好，因为它不具备无后效性，因为它的第n+1的数会影响前n个序列的长度，换句话说，如果第n+1个数加上去不一定使得和前n个数加起来就是最长子序列，具体例子很多比如5,6,1,2 第5个数是3，那么最长序列5,6加3不会比1,2加3长。

比较好的子问题是“求以第K个为终点的最长上升子序列”，其实这个子问题的好处在于它限定了一点，终点为第k个数，那么我去递推第K+1的最长子序列时，它只跟前面各个以某点为终点的最长子序列有关

接下来，我们写出它的状态转移方程

maxLen（k）表示为ak作为终点的最长上升子序列的长度

初始状态：maxLen（1）=1

maxLen（k）=max{ maxLen（i）:1<=i<k且ai < ak 且k>=2}+1

若找不到则maxLen（k）=1

因为以小于ak为终点的各序列，若满足上述条件，加上ak，一定会形成更长的上升子序列。

另外从认识的角度讲，ak是从终点1到k-1一个个判断下来的，那么一旦他们两个是上升的，连带的会把ai的最长子序列长度带上去，使之变得更长。

本题仅作了一个小的改动最长上升总和，思路大致相同，代码如下

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define MAXN 1005

 using namespace std;

 int num[MAXN],m[MAXN];//m记录以每个终点的最长上升总和

 int main()

 {

     int t,i,j,k;

     while(cin>>t)

     {

         if(t==)

             break;

         memset(m,,sizeof());

         for(i=;i<=t;i++)

             scanf("%d",&num[i]);

         m[]=num[];

         for(i=;i<=t;i++)

         {

             m[i]=num[i];

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

             {

                 if(num[j]<num[i])

                     m[i]=max(m[i],m[j]+num[i]);

             }

         }

         k=m[];

         for(i=;i<=t;i++)

             k=m[i]>k?m[i]:k;

         cout<<k<<endl;

     }

     return ;

 }

巴特西

动态规划专题（一） HDU1087 最长公共子序列

最新文章

热门文章