hdu 1087 Super Jumping! Jumping! Jumping!（LIS）

Super Jumping! Jumping! Jumping!

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1087

解题思路：

dp[i]表示以value[i]结尾的最大价值。则状态转移方程为dp[i]=max(dp[j]+value[i],value[i])  其中(value[j]<value[i],表示i可以从j跳过去)

(0<=j<i)。

AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int dp[N];
int value[N];

int main(){
    int n;
    while(scanf("%d",&n),n){
        for(int i = 0; i < n; i++)
            scanf("%d",&value[i]);
        dp[0] = value[0];
        int ans = 0;
        for(int i = 1; i < n; i++){
            dp[i] = value[i];
            for(int j = 0; j < i; j++){
                if(value[i]>value[j] && dp[i] < dp[j]+value[i]){
                        dp[i] = dp[j]+value[i];
                }
            }
            if(dp[i] > ans)
                ans = dp[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}