爱华网Super Jumping! Jumping! Jumping!
TimeLimit: 2000/1000 MS(Java/Others)MemoryLimit: 65536/32768 K (Java/Others)Total Submission(s):7910AcceptedSubmission(s): 3183
Problem DescriptionNowadays, a kind of chess game called “Super Jumping! Jumping!Jumping!” is very popular in HDU. Maybe you are a good boy, andknow little about this game, so I introduce it to you now.
The game can be played by two or more than two players. It consistsof a chessboard（棋盘）and some chessmen（棋子）, and all chessmen aremarked by a positive integer or “start” or “end”. The player startsfrom start-point and must jumps into end-point finally. In thecourse of jumping, the player will visit the chessmen in the path,but everyone must jumps from one chessman to another absolutelybigger (you can assume start-point is a minimum and end-point is amaximum.). And all players cannot go backwards. One jumping can gofrom a chessman to next, also can go across many chessmen, and evenyou can straightly get to end-point from start-point. Of course youget zero point in this situation. A player is a winner if and onlyif he can get a bigger score according to his jumping solution.Note that your score comes from the sum of value on the chessmen inyou jumping path.
Your task is to output the maximum value according to the givenchessmen list.
InputInput contains multiple test cases. Each test case is described ina line as follow:
N value_1 value_2 …value_N
It is guarantied that N is not more than 1000 and all value_i arein the range of 32-int.
A test case starting with 0 terminates the input and this test caseis not to be processed.
OutputFor each case, print the maximum according to rules, and one lineone case.
Sample Input3 1 32 4 1 2 3 4 4 3 3 2 1 0
Sample Output4 103早上有些事，耽误了做题，为了赶上吃中午饭，所以找到简单的做。虽然没一点DP感觉，但在我不懈的努力下，应该能明白DP是个什么东西的。英语不好一直很令人头疼，就比如这道题，是看数据才看懂的，在我看来，数据都比英语好看。解释一下题意：此题就是找序列中最大升序子序列的和。比如 1 3 2中升序序列有：｛1｝｛3｝｛2｝｛1，3｝｛1，2｝。所以最大为1+3=4；
定义两个数组：b[i]存i位置的数，dp[i]存i位置的最大和。状态方程： dp[i]=max {dp[j](if(b[j]<b[i])) }+ b[i] ,其中j<i。代码注意处理下dp[0]就行。下面是AC代码：#include<iostream>using namespace std;int main(){int n;while(scanf("%d",&n)!=EOF&&n){int dp[1010]={0};//最大和int b[1010]={0};//当前数for(int i=0;i<n;i++){int temp;int max=-1;scanf("%d",&temp);b[i]=temp;bool find=false;for(int j=0;j<i;j++){if((b[j]<temp)&&(dp[j]+temp>max)){max=dp[j]+temp;find=true;}}if(find) dp[i]=max;else dp[i]=b[i];}int out=-1;for(int i=0;i<n;i++){if(out<dp[i]) out=dp[i];}cout<<out<<endl;}return 0;}因为急着回家吃饭，所以写的不规矩...另外发现：写ACM题关键就是模拟计算机处理问题的环境，给他创造一个尽可能短跑道使得他能跑道目的地。其实算法也是一种模拟！是一种对想法的模拟。哎呀呀，心情舒畅，得意的笑，这么多天总算有点收获……
