Super Jumping! Jumping! Jumping!
Time Limit: 2000/1000 MS(Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13618Accepted Submission(s): 5689
Problem Description
Nowadays,a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popularin HDU. Maybe you are a good boy, and know little about this game, so Iintroduce it to you now.
The game can be played by two or more than two players. It consists of achessboard(棋盘)andsome chessmen(棋子),and all chessmen are marked by a positive integer or “start” or “end”. Theplayer starts from start-point and must jumps into end-point finally. In thecourse
of jumping, the player will visit the chessmen in the path, but everyonemust jumps from one chessman to another absolutely bigger (you can assumestart-point is a minimum and end-point is a maximum.). And all players cannotgo backwards. One jumping can go from
a chessman to next, also can go acrossmany 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 andonly if he can get a bigger score according to his jumping solution.
Note thatyour 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 testcase 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 rangeof 32-int.
A test case starting with 0 terminates the input and this test case is not tobe processed.
Output
For each case, print the maximum according torules, 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
第一次做动态规划的题目!AC了,很开心!发一下代码!
//第一次做动态规划的题目,希望自己用心做!能够做对吧!
//第一次动态规划总算弄对了!
#include<iostream>
using namespace std;
int main()
{
int n;
int i,j,max,max1;
int w[1002],dp[1002];
while(cin>>n)
{
if(n==0) break;
for(i=0;i<n;i++)
cin>>w[i];//一个个输入节点上的值
//接下来就是动态规划了!从前向后搜!
//状态转移!dp[i]表示以i节点为终点,获得总分最大的值
//dp[i]=min{dp[k]+w[i],w[i]}
//试一试!
dp[0]=w[0];//从第一个点开始,以第一个点为终点,其值一定为w[0];
max=dp[0];
for(i=1;i<n;i++)
{ dp[i]=w[i];
//max1=w[i];
for(j=0;j<i;j++)
if(w[i]>w[j] && dp[j]+w[i]>dp[i])
{
//max1=dp[j]+w[i];
dp[i]=dp[j]+w[i];
}
}
for(i=0;i<n;i++)
if(dp[i]>max)
max=dp[i];
cout<<max<<endl;
}
}
分享到:
相关推荐
杭电oj1000题解题报告
杭电OJ题目分类的叙述,可以方便去学习去做。
杭电OJ 2028代码 the rosolve of the hdu 2028
杭电OJ(1000-1099) AC 代码
本资源主要提供了杭电oj题目分类和自测状况两大类 可实现随机选题等功能.
杭电OJ部分威士忌的代码 杭电OJ部分威士忌的代码杭电OJ部分威士忌的代码
杭电oj上的一些疑问,适用于初学者,可以解答一些疑问 都是一些水题
杭电oj 1047习题
杭电oj分类
杭州电子科技大学 oj离线版
这是HDUOJ上面的140道题目的答案,其中大部分都是简单题,有些太简单的就没有收集进去,代码为C/C++,全都AC了的,其中有些有具体的说明是怎么做的,例如博弈论那些
课程资源 杭电OJ1000-1099答案 ,仅供参考...
杭电oj的离线版以及题目分类的文档 更加一目了然 方便选择适合的题目做 适合暂时上不了网的用于练习
这是杭电OJ上某些题的解题报告,后续还有上传很多!
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
杭电oj1048答案,c++代码,适合初学者,思路简单
杭电ACM2000-2011题已提交的代码!保证正确!
杭电离线oj(2010版),方便不能上网的朋友用,比别的版本增加了很多题!