Super Jumping! Jumping! Jumping!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 32564 Accepted Submission(s):
14692
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.
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.
and one line one case.
4 1 2 3 4
4 3 3 2 1
0
| 下标i | 0 | 1 | 2 | 3 | 4 | 5 |
| a[i] | ||||||
| sum[i] | 3 | 2 | 7 | 2 | 5 | 13 |
| ans | 0 | 3 | 7 | 7 | 5 | 13 |
#include <iostream>
#include <cstdio>
//#define max(a,b) a>b ? a:b
using namespace std; int main()
{
int n;
int a[];//存储每一个数
int sum[];//存储这个数之前的递增子序列的和
int ans;//一直存储最大的和
while(scanf("%d",&n)!=EOF && n!=){
for(int j1=;j1<n;j1++){
scanf("%d",&a[j1]);
}
sum[]=a[];
ans=;
for(int i= ;i<n;i++){
ans=;
for(int j=;j<i;j++){
if(a[i]>a[j]){
ans=max(sum[j],ans);//重要代码！
}
}
sum[i]=a[i]+ans;//重要代码！
}
ans=-;
for(int i=;i<n;i++){
if(ans<sum[i]){
ans=sum[i];
}
}
cout<<ans<<endl;
}
return ;
}
我是代码，请点我！！！
不懂的时候，告诉自己，再坚持一下，再坚持一下，这个题就看懂了。
刚开始不会做，然后百度，看了好久才看明白这个题的方法~~~~(>_<)~~~~