Super Jumping! Jumping! Jumping!(最优子序列)(hdu1087)

//hdu1087  Super Jumping! Jumping! Jumping!

此题并非求最优子序列的长度，而是要求最优子序列的和。

算法总结：

每做一步时，不是保存序列的长度opt[]，而是保存序列的最大值sum[]。

 类似的公式opt[i]= 1  (i=1)

                    max{opt[j]}+1 (i>1&&1<=j；；；

         sum[i]= a[1] (i=1)

                 max{sum[j]}+a[i] (i>1&&1<=j

上面公式中出现的1以及a[i]都是代表当前元素(也即是a[i])。

代码如下：

#include

#define size 1001

using namespace std;

//求最大上升子序列  的值

//直接将最大上升子序列  和保存到sum[]中

/*9

1 4 7 2 5 8 3 6 9:29

9

1 4 2 5 7 3 8 6 9:34

*/

__int64 opt[size],sum[size],a[size],max1;

 

int main()

{

 int n,i,j;

 while(cin>>n&&n)

 {

     for(i=1;i<=n;i++)

         scanf("%I64d",&a[i]);

     for(i=0;i<=n;i++) sum[i]=0;

     opt[1]=1;

 

     sum[1]=a[1];

    for(i=2;i<=n;i++)

    {max1=0;//max必须赋值为0

        for(j=1;j

        {if(a[i]>a[j])

           if(max1

           {max1=sum[j];

           }

        }//for j

      sum[i]=max1+a[i];

    }

 

    max1=0;

    for(i=1;i<=n;i++) if(sum[i]>max1) max1=sum[i];

 

    printf("%I64d\n",max1);

 }//while cin n

 

 return 1;

}