Super Jumping! Jumping! Jumping!（初学者也能看懂的dp）

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

题意很简单，就是给一个n，然后输入n个数，找到其中的最长递增的子序列。（很明显，用dp）

要注意，用dp是因为：如果你直接就比较找答案，极有可能找到的不是最优解。（初学者容易犯的错误）

例如：5 6 7 1 2 3 4 5 6 7 8

直接比较找答案的结果：5 6 7 8  总和为26

用dp的结果：1 2 3 4 5 6 7 8      总和为36

感兴趣的可以试一下，看结果是不是这样。我会把两种方法的代码贴上去（都很短），比较一下。

回到正题，讲一下dp的做法：

状态转移方程：

dp[i] = max(dp[i],dp[j]+num[i]);//dp[i]代表当前状态的总和，dp[j]代表上一个数的状态的总和，num[i]代表当前的数。

上dp代码：

#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <sstream>
#include <map>
#include <cctype>

using namespace std;
#define Start clock_t start = clock();
#define End clock_t end = clock();
#define Print cout<<(double)(end-start)/CLOCKS_PER_SEC*1000<<"ºÁÃë"<<endl;

const int maxn = 10000 + 5;

int dp[maxn],num[maxn];
int main()
{
    int n;
    while(cin>>n && n){
        memset(dp,0,sizeof(dp));
        int maxi = 0;
        for(int i = 0;i < n;i++)
            cin>>num[i];
        dp[0] = num[0];
        for(int i = 1;i < n;i++){
            //dp[i] = num[i];//34行就是这一处
            for(int j = 0;j < i;j++){
                if(num[i] > num[j]){
                    //dp[i]代表当前状态的总和，dp[j]代表上一个数的状态的总和，num[i]代表当前的数。
                    dp[i] = max(dp[i],dp[j]+num[i]);
                }
            }
            dp[i] = max(dp[i],num[i]);//这里有个技巧，此处的效果和34行的效果一样
        }
        for(int i = 0;i < n;i++){
            maxi = max(dp[i],maxi);
        }
        cout<<maxi<<endl;
    }

    return 0;
}

现在给的是直接比较找答案的方法（错误的方法，但是初学者可能一开始会这么做。）

#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <sstream>
#include <map>
#include <cctype>

using namespace std;
#define Start clock_t start = clock();
#define End clock_t end = clock();
#define Print cout<<(double)(end-start)/CLOCKS_PER_SEC*1000<<"ºÁÃë"<<endl;

const int maxn = 1000000 + 5;

int a,b;
int main()
{
    int n;
    while(cin>>n && n){
        int ans = 0;
        b = 0;
        for(int i = 0;i < n;i++){
            cin>>a;
            if(a > b) {b = a;ans += a;}
            else continue;
        }
        cout<<ans<<endl;
    }

    return 0;
}

希望我的文章能给你们带来帮助，请点赞！