HDU 1087 Super Jumping! Jumping! Jumping! (DP)，hdu1087

HDU 1087 Super Jumping! Jumping! Jumping! (DP)，hdu1087

C - Super Jumping! Jumping! Jumping! Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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. 



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     即求最大升序子串，可以不連續，但是s[i]一定要大於s[i-1]。 思路是從後面開始算，把每個以此位置為起點的最大升序子串的和求出來，存DP數組裡。比如只有1 2 99 97 98這三個元素(同時這也是一組易錯的數據)，那就從98開始算，98的最大升序子串和顯然是98，所以DP[4]=98。然後開始算97，97的算法是找出它後面所有比它大的，然後比較它們的DP值，取最大的那一個，加上97即可，因為後面只有一個98，98大於97，所以97這個位置的DP值就是97 + 98，即以97為起點的升序子串為97 98。再算99，後面所有數都比它小，不可取，所以DP值是它本身。又算2，顯然後面的所有數都比它大，所以都可以取，但是我們要取DP值最大那個，即97的(195)，同理，1也是這麼算，最後算出來1的DP值是198，最大，就取它了。推廣到一般情況，最後算出答案後要遍歷一次DP數組，因為最後的答案可能不是以第一個元素為起點。  

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define    MAX    1005
 5 
 6 int    main(void)
 7 {
 8     int    n;
 9     int    s[MAX];
10     int    dp[MAX],max,ans;                        //dp[i]存的是以i為起點的最大升序子串的和
11 
12     while(scanf("%d",&n) && n)
13     {
14         for(int i = 0;i < n;i ++)
15             scanf("%d",&s[i]);
16 
17         ans = dp[n - 1] = s[n - 1];
18         for(int i = n - 2;i >= 0;i --)            
19         {
20             max = 0;
21             for(int j = i + 1;j < n;j ++)         //看s[i]後面哪一個子串是s[i]可以加進去的,找出所有這樣的子串,取DP值最大那個
22                 if(s[i] < s[j] && max < dp[j])
23                     max = dp[j];
24             dp[i] = s[i] + max;
25 
26             ans = ans < dp[i] ? dp[i] : ans;
27         }
28         ans = ans < 0 ? 0 : ans;                 //注意可以從起點直接跳終點,此時值為0,若是算出最終值是負數的話要選此方案
29         
30         printf("%d\n",ans);
31     }
32 
33     return    0;
34 }