注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 1087 Super Jumping! Jumping! Jumping!  

2014-03-22 00:12:31|  分类: DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Super Jumping! Jumping! Jumping!

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


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.

HDU 1087 Super Jumping! Jumping! Jumping! - 983433479 - 983433479的博客


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
 

Author
lcy
 

Recommend
We have carefully selected several similar problems for you:  1069 1058 1203 1231 1421 

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
int i,j,n,a[10000],sum[10000],max;
while(cin>>n,n)
{
memset(a,0,sizeof(a));
memset(sum,0,sizeof(sum));
for( i=0;i<n;i++)
{
cin>>a[i];
sum[i]=a[i];
}
max=a[0];
for(i=0;i<n;i++)
{
for( j=0;j<i;j++)
{
if(a[i]>a[j]&&sum[i]<sum[j]+a[i])// sum[i]=max(sum[j])+a[i],减少运算量;
{
sum[i]=sum[j]+a[i];
}
if(sum[i]>max)
{
max=sum[i];
}
}

}
cout<<max<<endl;

}
return 0;
}


 
  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017