Problem C
Time Limit : 2000/1000ms (Java/Other) Memory Limit :65536/32768K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 2
Problem Description
Nowadays, a kind of chess gamecalled “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you area good boy, and know little about this game, so I introduce it to younow.<br><br><center><imgsrc=/data/images/1087-1.jpg></center><br><br>The game canbe played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are markedby a positive integer or “start” or “end”. The player starts from start-pointand must jumps into end-point finally. In the course of jumping, the playerwill visit the chessmen in the path, but everyone must jumps from one chessmanto another absolutely bigger (you can assume start-point is a minimum andend-point is a maximum.). And all players cannot go backwards. One jumping cango from a chessman to next, also can go across many chessmen, and even you canstraightly get to end-point from start-point. Of course you get zero point inthis situation. A player is a winner if and only if he can get a bigger scoreaccording to his jumping solution. Note that your score comes from the sum ofvalue on the chessmen in you jumping path.<br>Your task is to output themaximum value according to the given chessmen list.<br>
Input
Input contains multiple testcases. Each test case is described in a line as follow:<br>N value_1value_2 …value_N <br>It is guarantied that N is not more than 1000 andall value_i are in the range of 32-int.<br>A test case starting with 0terminates the input and this test case is not to be processed.<br>
Output
For each case, print themaximum according to rules, and one line one case.<br>
Sample Input
3 1 3 2
4 1 2 3 4
4 3 3 2 1
0
Sample Output
4
10
3
算法分析：
跟求最长不下降子序列一个思路，只不过这里要求的是和最大不下降的子序列。
代码实现：
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,i,j;while(~scanf("%d",&n)&&n){int num[1005],sum[1005],maxx;//sum[i]表示前i个不下降子序列的最大和memset(sum,0,sizeof(sum));for(i=1;i<=n;i++){scanf("%d",&num[i]);sum[i]=num[i]; //初始化，每一个至少包括它本身}for(i=1;i<=n;i++){maxx=-999999;for(j=1;j<=i-1;j++){if(num[j]<num[i]&&sum[j]>maxx)//找前面和最大的不下降子序列{maxx=sum[j];}}if(maxx>0) //找到满足，sum[i]加上{sum[i]+=maxx;}}maxx=sum[1];for(i=2;i<=n;i++)if(sum[i]>maxx)maxx=sum[i];cout<<maxx<<endl;}return 0;
}