303 - 買醬油IV 之 商店問題

ForTest

題目：http://hoj.twbbs.org/judge/problem/view/303
AC code：http://ideone.com/uZEIoK
找出字典序最小的LIS
也就是從後面開始做LDS
詳細證明見演算法筆記
http://www.csie.ntnu.edu.tw/~u91 ... gSubsequence.html#3

Submission id:19877 Status:AC
http://hoj.twbbs.org/judge/judge/submission/19877

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#include <map>

#include <queue>

#include <sstream>

using namespace std;

#define F(a,b) for(int a=0;a<b;++a)

typedef long long LL;

const int Max = 1e5 + 10;

LL n,ans,p[Max],s[Max];

vector<LL> lis;

bool cmp(LL a,LL b){ return a > b; }

void Lis(){

    int pos = 0;

    for(int i=n-1;i>=0;--i)

        if((i == n-1) || (s[i] < lis.back())){

            lis.push_back(s[i]);

            p[i] = (++pos);

        }

        else{

            vector<LL>::iterator l = lower_bound(lis.begin(),lis.end(),s[i],cmp);

            *l = s[i];

            p[i] = l - lis.begin() + 1;

        }

    F(i,n) if(p[i] == pos){

        ans += i+1;

        pos --;

    }

}

int main(){

    scanf("%lld",&n);

    F(i,n) scanf("%lld",&s[i]);

    Lis();

    printf("%lld\n",ans);

}