HDU1087 Super Jumping! Jumping! Jumping! —— DP_alince20008的博客-程序员秘密

技术标签: java  php  数据结构与算法  

题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1087

 

Super Jumping! Jumping! Jumping!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 41523    Accepted Submission(s): 19239


Problem Description
Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.



The game can be played by two or more than two players. It consists of a chessboard(棋盘)and some chessmen(棋子), and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.
Your task is to output the maximum value according to the given chessmen list.
 

 

Input
Input contains multiple test cases. Each test case is described in a line as follow:
N value_1 value_2 …value_N 
It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.
A test case starting with 0 terminates the input and this test case is not to be processed.
 

 

Output
For each case, print the maximum according to rules, and one line one case.
 

 

Sample Input
3 1 3 2 4 1 2 3 4 4 3 3 2 1 0
 

 

Sample Output
4 10 3
 
 
题解:
类似于最长上升子序列, 只不过把dp[i]从个数,变为数值之和。
 
 
代码如下:
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 #define ms(a,b) memset((a),(b),sizeof((a)))
13 using namespace std;
14 typedef long long LL;
15 const double EPS = 1e-8;
16 const int INF = 2e9;
17 const LL LNF = 2e18;
18 const int MAXN = 1e3+10;
19 
20 int a[MAXN], dp[MAXN];
21 int n;
22 
23 int main()
24 {
25     while(scanf("%d", &n) &&n)
26     {
27         for(int i = 1; i<=n; i++)
28             scanf("%d", &a[i]);
29 
30         ms(dp, 0);
31         for(int i = 1; i<=n; i++)
32         for(int j = 0; j<i; j++)
33             if(j==0 || a[i]>a[j])
34                 dp[i] = max(dp[i], dp[j]+a[i]);
35 
36         int ans = -INF;
37         for(int i = 1; i<=n; i++)
38             ans = max(ans, dp[i]);
39         printf("%d\n", ans);
40     }
41 }
View Code

 

转载于:https://www.cnblogs.com/DOLFAMINGO/p/7624544.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/alince20008/article/details/102256853

智能推荐

Arcmap高级标注(通过表达式设置颜色/字体/换行等)_weixin_30765475的博客-程序员秘密

python下多字段换行堆叠不同字体颜色显示:def FindLabel ( [bz], [Id] ): return "&lt;CLR red='255'&gt;&lt;FNT size='20'&gt;"+[bz]+"&lt;/FNT&gt;&lt;/CLR&gt;"+'\n'+"&lt;CLR green='255'&gt;&lt;FNT size='16'&gt;"+ [Id] ...

html 渐变透明写法,css实现文字颜色渐变的三种方法_weixin_40008644的博客-程序员秘密

在web前端开发过程中,UI设计师经常会设计一些带渐变文字的设计图,在以前我们只能用png的图片来代替文字,今天可以实现使用纯CSS实现渐变文字了。下面就介绍3中实现方式供大家参考!基础样式:.gradient-text{text-align: left;text-indent:30px;line-height: 50px;font-size:40px;font-weight:bolder; po...

android 修改系统属性函数,Android常用修改_糕图图的博客-程序员秘密

设置系统默认语言或者设备版本型号属性一般途径1)进入build/target/product目录,修改文件core_base.mk的PRODUCT_PROPERTY_OVERRIDES 值,例如,欲修改为默认中文,则增加语句如PRODUCT_PROPERTY_OVERRIDES := \ro.config.notification_sound=OnTheHunt.ogg \ro.config.al...

java 设计模式 状态模式_loveblog1314的博客-程序员秘密

之前有一个需求,是学生答卷之后,根据不同的得分,进行不同的提分流程操作,当时写功能的时候,针对提分流程的操作,写了一大堆if……else操作,最近在思考代码美化的过程,突然发现此流程可以使用 状态模式 来代替,重新查了一下 设计模式-状态模式 的实现:身为程序员,废话不多说,直接上例子,例子是写书的过程的例子:写书分为多个过程:开始构造,草稿,发布,完成通用接口:public in

elasticsearch集群部署_da_kiku的博客-程序员秘密

Elasticsearch集群部署一、集群es1、拉取镜像docker pull elasticsearch:6.8.82、创建配置文件存放目录cd ~/es-clustermkdir es1mkdir es23、创建配置文件cd es1vim elasticsearch.yml添加以下内容cluster.name: my-elasticsearch #集群名称network.host: 0.0.0.0node.name: node-1 #节点名称#集群节点discov

es6 获取url参数-程序员秘密

function GetQueryString(name) { var reg = new RegExp("(^|&amp;)" + name + "=([^&amp;]*)(&amp;|$)"); console.log(window.location.search)//?id=2 var r = window.location.search.substr(1).match(reg); if (r != null) return unescape(r[2]); re

随便推点

学习笔记:GoogLeNet_Eloudy的博客-程序员秘密

这么旁征博引的博文,能不转么  GoogLeNet, 2014年ILSVRC挑战赛冠军,将Top5 的错误率降低到6.67%. 一个22层的深度网络,论文在http://arxiv.org/pdf/1409.4842v1.pdf,题目为:Going deeper with convolutions。(每次看这么简洁优雅的题目,就想吐槽国内写paper的 八股文题目)。G

蓝桥杯 ALGO-53 算法训练 最小乘积(基本型)_mainn的博客-程序员秘密

算法训练 最小乘积(基本型)  时间限制:1.0s   内存限制:512.0MB    问题描述  给两组数,各n个。  请调整每组数的排列顺序,使得两组数据相同下标元素对应相乘,然后相加的和最小。要求程序输出这个最小值。  例如两组数分别为:1 3  -5和-2 4 1  那么对应乘积取和的最小值应为:  (-5) * 4 + 3 *

Linux pwn入门教程(0)——环境配置_dfdhxb995397的博客-程序员秘密

作者:[email protected]×00前言作为一个毕业一年多的辣鸡CTF选手,一直苦于pwn题目的入门难,入了门更难的问题。本来网上关于pwn的资料就比较零散,而且经常会碰到师傅们堪比解题过程略的writeup和没有注释,存在大量硬编码偏移的脚本,还有练习题目难找,调试环境难搭建,GDB没有IDA好操作等等问题。作为一个老萌新(雾),决定依据Atum师傅在i春秋上的p...

Python自动化开发学习的第一周----python基础学习_weixin_34417814的博客-程序员秘密

1.Python的发展史1989年,为了打发圣诞节假期,Guido开始写Python语言的编译器。Python这个名字,来自Guido所挚爱的电视剧Monty Python’s Flying Circus。他希望这个新的叫做Python的语言,能符合他的理想:创造一种C和shell之间,功能全面,易学易用,可拓展的语言。1991年,第一个Python编译器诞生。它是用C语言实现的,并能...

网络流24题4 魔术球问题 ssl 2604 code[vs] 1234_A_loud_name的博客-程序员秘密

Description假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,…的球。 (1)每次只能在某根柱子的最上面放球。 (2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。 试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可放 11 个球。 对于给定的 n,计算在 n 根柱子上最多能放多少个球。Input第

【人工智能】Benchmark、SOTA、Baseline_人工智能sota什么意思_Chris Brown的博客-程序员秘密

人工智能中的Benchmark、SOTA、Baseline指的是什么?SOTASOTA(state-of-the-art)指的是针对于某一种特定任务,该模型做到了最佳,即最佳性能算法。BenchmarkBenchmark同后文需要讲到的Baseline比较像,都是用于对比不同模型准确度,性能表现等方面的概念。一个模型能够作为Benchmark,那么其一定是业内已经研究比较成熟,得到了较多认可的。比如经典数据结构和算法中的栈、队列等数据结构,亦或者是二分查找、哈希查找等算法,他们都可以用于对新模型的