HOJ 1087 Super Jumping!（最长严格递增子序列）

最长严格递增子序列
题目意思：
求解最大递增子序列和，这里要特别注意一点：这个题目不要求是连续的最大递增子序列。
但是一定要注意是递增的！！
本题要点：
1、裸题的 LIS. n <= 1000, 复杂度 O(n^2).
dp[i] 表示以i结尾的，最长严格递增子序列总和.然后套用 LIS 的模板， 得到数组 dp, 在dp 中找到最大值即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 1010;
long long h[MaxN];
long long dp[MaxN];	// dp[i] 表示以i结尾的，最长严格递增子序列总和
int n;void solve()
{
    long long ans = h[1];dp[1] = h[1];for(int i = 2; i <= n; ++i){
    int max_sum = h[i];for(int j = 1; j < i; ++j){
    if(h[j] < h[i]){
    if(max_sum < dp[j] + h[i]){
    max_sum = dp[j] + h[i];}}}dp[i] = max_sum;if(ans < dp[i]){
    ans = dp[i];}}printf("%lld\n", ans);
}int main()
{
    while(scanf("%d", &n) != EOF && n){
    for(int i = 1; i <= n; ++i){
    scanf("%lld", &h[i]);}solve();}return 0;
}/* 3 1 3 2 4 1 2 3 4 4 3 3 2 1 0 *//* 4 10 3 */