HDU 1078 Super Jumping! Jumping! Jumping!

题意： 有这么个游戏，从start到end（自己决定在哪停下来）连续跳圈，中间不能空一个圈不跳，圈里的数字必须比你上次跳到圈里的数字大，最后求你所有路过的圈中数字总和最大。

思路：很明显的最长上升子序列之和，状态方程就是：

dp[i] = max(dp[i],dp[j]+a[i])(a[i]>a[j]，且i>j,dp[i]是i当前最优状态)

/**

Sample Input

3 1 3 2

4 1 2 3 4

4 3 3 2 1

0 

Sample Output

4

10

3

**/

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int dp[1005];

int a[1005];

int main(){

    int n;

    while(~scanf("%d",&n)){

        if(!n) break;

        for(int i=0;i<n;i++){

            scanf("%d",&a[i]);

        }

        int res = 0;

        for(int i=0;i<n;i++){

            dp[i] = a[i];

            for(int j=0;j<i;j++){

                if(a[i]>a[j]){

                    dp[i] = max(dp[i],dp[j]+a[i]);

                }

            }

            res = max(res,dp[i]);//每次保存最优

        }

        printf("%d\n",res);

    }

    return 0;

}