Super Jumping! Jumping! Jumping!
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16653Accepted Submission(s): 7093
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
最大递增子段和,状态方程:sum[j]=max{sum[i]}+a[j];
其中,0<=i<=j,a[i]<a[j]
#include <iostream>
using namespace std;
int arr[1001];
int n;
int opt[1001];
int main() {
int max=0;
while (cin >> n, n) {
for (int i = 0; i < n; i++) {
cin >> arr[i];
if(arr[i] > max)
max = arr[i];
}
//状态方程:opt[j]=max{opt[j]}+a[i]; 其中,0<=j<i,a[j]<a[i]
opt[0] = arr[0];
int max = 0;
for(int i=1; i<n; i++){
max = 0;
for(int j=0; j<i; j++){
if(opt[j] > max && arr[j] < arr[i])
max = opt[j];
}
opt[i] = max + arr[i];
}
max = 0;
for(int i=0; i<n; i++)
if(opt[i] > max)
max = opt[i];
cout << max <<endl;
}
return 0;
}
分享到:
相关推荐
1001 计算直线的交点数 1002 FatMouse's Speed1003 Common Subsequence1004 Max Sum 1005 Super Jumping! Jumping! Jumping! 1006 免费馅饼 1007 Humble Numbers1008 Monkey and Banana 1009 龟兔赛跑 1010 数塔
Alex Allain - Jumping into C++ (with Sample Code) http://www.cprogramming.com/c++book/?inl=ft-nhp (this website alway be my online references for C/C++)
PRO-C21-JUMPING-BOX
app-ski-jumping-mm tupij wpiszemy schematfolderówIarchitekturęprojektu 包装型号:wszystkie encje
PRO-C21-JUMPING_BOX
游戏一个游戏! 大概。
2-104兔子跳小游戏Blocky rabbit jumping 1.12-104兔子跳小游戏Blocky rabbit jumping 1.12-104兔子跳小游戏Blocky rabbit jumping 1.12-104兔子跳小游戏Blocky rabbit jumping 1.12-104兔子跳小游戏Blocky rabbit ...
C-21跳箱子
蹦极跳系统的仿真,整个蹦极跳系统的数学描述为mx =mg+bx-a1x -a2|x |x ,m为物体的重量,g为重力加速度,x为物体的位置。
Jumping_into_c++
C21-JUMPING
带有状态依赖时滞的马尔科夫跳基因调控网络的鲁棒稳定性,张文兵,方建安,这篇文章中,我们研究了带有状态依赖时滞和参数不确定马尔科夫跳基因调控网络的鲁棒稳定性问题,状态依赖时滞存在于翻译和调控过
在命令行中: khinsider.py jumping-flash 作为进口: import khinsiderkhinsider . download ( 'jumping-flash' )# And bam, you've got the Jumping Flash soundtrack! 有关动漫音乐, 。 仔细地把它们放在一起!...
Jumping into C++ 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
调用java源码云跳java 这是我在2012 Dreamforce会话中称为“ Cloud Jumping”的源代码
Jumping Into C++高清文字版本. Want to learn to code? Want to learn C++? Struggling to follow your lecturer or books and tutorials written for experts? You're not alone. As a professional C++ developer...
每小时日志-袋鼠跳 EmilyMüller-Teusler和Maxine Motzkus着阿伦斯堡斯托纳姆学校12b类2020/21学年 内容 十二月 一月 二月 行进 2021年3月5日,星期四 2021年3月9日,星期二 2021年3月11日,星期四 ...
楼下跳球图形设计了一个穿过楼梯的球。 每个楼梯跳跃的帧用于绘制运动感。
pro21跳箱
在打开此页面 用作扩展 该存储库可以作为扩展添加到MakeCode中。 打开 ...搜索并导入 编辑这个专案 在MakeCode中编辑此存储库。... 单击导入,然后单击导入URL ...此图显示了master中最后一次提交的块代码。...