HDU - 1087 Super Jumping! Jumping! Jumping!（LIS，最大上升子序列求和，nlogn做法）

HDU - 1087

因为这道题数据范围比较小，暴力n^2做法就可以AC，

后面给大家介绍一种 当 1<n<100000,需要用到 $O(nlogn)$ 的时间复杂度

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1010],a[1010];
int main()
{
    int n;while(scanf("%d",&n)&&n){
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){
    dp[i]=a[i];for(int j=1;j<i;j++)if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+a[i]);}int ans=0;for(int i=1;i<=n;i++) ans=max(ans,dp[i]);printf("%d\n",ans);}return 0;
}

$O(nlogn)$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100005;
int n,a[N],diff[N],sz;// 离散化
ll c[N];// 树状数组
inline void add(int x, const ll y) 
{
    for (;x<=n;x+=x&-x) c[x]=max(c[x],y);
}
inline ll Sum(int x) 
{
    ll res=0;for (;x;x&=x-1) res=max(res,c[x]);return res;
}
int main() {
    while(scanf("%d", &n)&&n){
    memset(c,0,sizeof c);for(int i=1;i<=n;i++) {
    scanf("%d",a+i);diff[i-1]=a[i];}sort(diff,diff+n);sz=unique(diff,diff+n)-diff;//排序后去重 ll res=0;for(int i=1;i<=n;i++) {
    a[i]=lower_bound(diff,diff+sz,a[i])-diff+1;//求出离散化之后的值ll f=diff[a[i]-1]+Sum(a[i]-1); //求出 f[i]。res=max(res,f),add(a[i],f);//更新答案并将 f[i] 存到树状数组中 a[i] 的位置。}printf("%lld\n",res);}return 0;
}