首页 > 其他 > 详细

HDU-1087-Super Jumping! Jumping! Jumping!:最简单的一道入门题

时间:2015-07-08 17:57:34      阅读:114      评论:0      收藏:0      [点我收藏+]

求递增子序列的最大和 
状态转移方程:table[i] = max(table[i]+value[j]) 前提value[i]>value[j], 构成递增】 
其中j from 0 to i-1  table[i]是前i个中的最优状态, value[j] 是 j 的价值 

#include<iostream>
using namespace std;
#define Size 1000
int main()
{
        int N;
        int value[Size+1];
        int table[Size+1];
        
        while( cin>>N&&N!=0 )
        {
                int ans=0;
                
                for( int i=0; i<N; i++ )
                {
                        cin>>value[i];
                        table[i]=value[i];
                        
                        for( int j=0; j<i; j++ )
                                if( value[i]>value[j] && value[i]+table[j]>table[i] )
                                        table[i] = value[i]+table[j];
                                        
                        if( table[i]>ans )
                            ans = table[i];
                }
                cout<<ans<<endl;
        }
        return 0;
}

  

HDU-1087-Super Jumping! Jumping! Jumping!:最简单的一道入门题

原文:http://www.cnblogs.com/FightForCMU/p/4630476.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!