HDU1087 Super Jumping! Jumping! Jumping!
发布日期:2022-02-25 01:17:47
浏览次数:65
分类:技术文章
本文共 2186 字,大约阅读时间需要 7 分钟。
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.
InputInput 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. OutputFor each case, print the maximum according to rules, and one line one case. Sample Input 3 1 3 24 1 2 3 44 3 3 2 10Sample Output
4103
解题思路
题目意思是求上升的子序列,并没有说是最大的,拿样例来说dp[0] = 1 dp[1] = 3,a[0] < a[1],所以dp[1] = dp[0] + a[1],可以推出状态转移方程为dp[i] = max(dp[i],dp[j] + a[i]);
#includeusing namespace std;int dp[10005];int a[10005];int main(){ int n; while(cin>>n && n != 0){ memset(dp,0,sizeof(dp)); for(int i = 0;i < n;i++){ cin>>a[i]; } int maxx = 0; dp[0] = a[0]; for(int i = 1;i < n;i++){ for(int j = 0;j < i;j++){ if(a[i] > a[j]){ dp[i] = max(dp[i],dp[j] + a[i]); } } dp[i] = max(dp[i],a[i]); } for(int i = 0;i < n;i++){ maxx = max(maxx,dp[i]); //printf("dp[%d] = %d\n",i,dp[i]); } cout< <
转载地址:https://blog.csdn.net/qq_37755550/article/details/80457035 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年05月03日 17时54分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Mybatis逆向工程的使用
2019-04-30
关于Hibernate的优缺点
2019-04-30
常用的 Maven 命令
2019-04-30
数据结构之顺序表的实现
2019-04-30
数据结构之线性链表
2019-04-30
JQuery使用validate插件完成校验
2019-04-30
关于java的继承
2019-04-30
关于java的内部类
2019-04-30
关于java的枚举
2019-04-30
一个简单的layui登陆界面
2019-04-30
使用Spring Boot写一个简单的Hello World
2019-04-30
Spring Boot整合Servlet使用
2019-04-30
SpringBoot 文件上传
2019-04-30
我居然在Github上找到了一个完整的停车系统(附源码地址)
2019-04-30
大厂经典面试题:Redis为什么这么快?
2019-04-30
培训班老师说可以用这个干掉一大批面试者
2019-04-30
阿里四面,居然栽在一道排序算法上
2019-04-30
【Java编码规范】《阿里巴巴Java开发手册(正式版)》发布!
2019-04-30
如何在二三线城市月薪过万(一)看完这篇后端简历优化,包你面试不断
2019-04-30