ACM DP Super Jumping! Jumping! Jumping!

秒速五厘米 2022-06-11 03:37 126阅读 0赞

滴，集训第十二天打卡。

这两天是DP，划水了一天的简单题，嘻嘻。

**HDU 1087 Super Jumping! Jumping! Jumping!**

**![20170729102835053][]**

**![20170729102906181][]**

题目大意：输入N,然后N个数的数组，求最大递增子序列的和。

思路：DP，i用来遍历数组，j用来计算0-i的最大值。

状态方程:sum\[i\]=max\{sum\[j\]\}+a\[i\];

#include <stdio.h>
    #include <algorithm>
    #include <string.h>
    using namespace std; 
    int a[1005],sum[1001];
    int main()//E
    {
    	int n,i,j,max,s;
    	while(scanf("%d",&n))
    	{
    		if(n==0)break;
    		for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
    	 	max=-9999;  
    	    memset(sum,0,sizeof(sum));    
    	    for(i=0;i<n;i++)
    		{  
    	        s=0;  
    	        for(j=0;j<i;j++)
    			{  
    	            if(a[j]<a[i])
    				{  
    	                if(s<sum[j])
                     	s=sum[j];  
    	            }  
    	        }  	  
    	        sum[i]=a[i]+s;  	  
    	        if(max<sum[i])  
             	max= sum[i];   
    	    }   
    	    printf("%d\n",max);
    	}
    }

[20170729102835053]: /images/20220611/59b1bb62ed4a498580d58950431e07ae.png
[20170729102906181]: /images/20220611/9dca7b0b93c34ed1b55a4e1ef9c7013f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关杭电-Super Jumping! Jumping! Jumping!（LIS）

Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Limit:

r囧r小猫/ 2022年08月10日 00:42/ 0 赞/ 145 阅读

相关 Super Jumping! Jumping! Jumping!（动态规划）

Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Lim

亦凉/ 2022年08月02日 13:58/ 0 赞/ 141 阅读

相关 HDOJ 1087-Super Jumping! Jumping! Jumping!【DP】

Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Limit:

女爷i/ 2022年07月26日 00:22/ 0 赞/ 145 阅读

相关 HDU 1080-Super Jumping! Jumping! Jumping!（LIS最长上升子序列-最大递增子段和）

Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Limit:

港控/mmm°/ 2022年07月24日 10:19/ 0 赞/ 486 阅读

相关 ACM DP Super Jumping! Jumping! Jumping!

滴，集训第十二天打卡。这两天是DP，划水了一天的简单题，嘻嘻。 HDU 1087 Super Jumping! Jumping! Jumping! ![2017072

秒速五厘米/ 2022年06月11日 03:37/ 0 赞/ 127 阅读

相关 hdu 1087 Super Jumping! Jumping! Jumping!

Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular

左手的ㄟ右手/ 2022年05月31日 02:08/ 0 赞/ 140 阅读

相关 HDU-1087-Super Jumping! Jumping! Jumping!（dp）

Super Jumping! Jumping! Jumping! Problem Description Nowadays, a kind of

小咪咪/ 2022年05月27日 04:35/ 0 赞/ 143 阅读

相关【hdu 1087】Super Jumping! Jumping! Jumping!

Problem Description： Nowadays, a kind of chess game called “Super Jumping! Jumping! Jum

骑猪看日落/ 2022年05月22日 21:18/ 0 赞/ 163 阅读

相关 Super Jumping! Jumping! Jumping!——————LIS的最大和

Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular

ゝ一纸荒年。/ 2022年05月17日 09:45/ 0 赞/ 143 阅读

相关 Super Jumping! Jumping! Jumping!（DP 最长不下降子序列）超详细题解

目录 1.题目 2.题意 3.解题思路 4.代码 1.题目

Dear 丶/ 2021年07月24日 12:07/ 0 赞/ 351 阅读