洛谷 P2008 大朋友的数字

DP,动态规划   树状数组   最长不下降子序列

by  GeneralLiu

题目

就是说给一串由 0~9 组成的序列

求 以 i (1~n) 结尾 的 最长不下降子序列 的 和

（最长不下降子序列不唯一时选编号字典序最小的）

解

两步

1 求最长不下降子序列

2 求 步骤1 的和

1

O(n^2) 暴力不必说 (因为数字只有 0~9 十个， 即10*n， 所以就是 O(n)啊)

O(n logn) 树状数组 log10≈3.几，即3*n 也可以算 O(n)啊；

对于 数值x 查询 以0~x结尾的 最长不下降子序列 长度

所得长度 +1 即为所求

用 树状数组 维护

！！！！

树状数组没有 0 啊

那就每个数 查询和更新 都加一

因为这个我卡了 TLE 当时相当不解

2

再开一个数组保存序列和

在步骤1中一起维护即可

详见代码 query() 和 update()

代码

#include<bits/stdc++.h>

using namespace std;

#define low k&-k

int ret,l,n,tree[],s[];

void query(int k){ //查询

    ret=s[k],l=tree[k]; //ret为序列和 l为长度 两个全局变量

    for(k-=low;k;k-=low)

        if(l<tree[k])//因为要保证字典序 所以 == 时 答案不改

            l=tree[k],ret=s[k]; //长度更改时 序列和才会更改

}

void update(int k){ //更新

    for(;k<=;k+=low)

        if(tree[k]<l) //因为要保证字典序 所以 == 时 不作修改

            tree[k]=l,s[k]=ret; //长度更新时 序列和才会更新

}

int main(){

    scanf("%d",&n);

    for(int v,i=;i<=n;i++){

        scanf("%d",&v);

        query(v+); //树状数组没有 0 要统一 +1

        ret+=v;

        l++;//长度再加上 本身

        printf("%d ",ret);

        update(v+);

    }

    return ;

}/*5

0 2 5 3 4*/