[HOJ 303]買醬油IV 之 商店問題

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

先備知識：最長嚴格遞增子序列、lower_bound和upper_bound的定義

為了方便說明：
1. 縮寫「最長嚴格遞增子序列」為LSIS
2. 定義S[i]為第i家商店的醬油價格
3. 定義L[i]為以S[i]為結尾的LSIS長度
4. 定義ANS[i]為以S[i]為結尾的LSIS中花費的最小精力

這裡假設你已經知道怎麼算每個L[i]
可以把我們的任務想成先求出最長的LSIS長度MAXL，並找出L[i]=MAXL的前提下，ANS[i]的最小值

那麼ANS[i]怎麼算呢？
現在，假設我們算到第i家商店，而我們也知道ANS[1~i-1]，並算出L[i]，可以考慮從L[0~i-1]之中找出所有L[j]=L[i]-1且S[j]<S[i]，取最小的ANS[j]，加上i便是ANS[i]了

為了降低時間複雜度，可以考慮對於每個長度LEN，維護一個二元組(LSIS結尾元素,最小精力)的集合，方式是在插入每一個值之前，利用類似單調對列的概念，刪除所有不可能是答案的點，取最小值時只要取upper_bound的前一個就好了，可以用map來實作

注意花費的精力可能會爆int(每家店都拜訪需要5000050000)，因此相關的數據要用long long處理

時間複雜度：O(NlogN)

ps.在我AC這題之後，HOJ馬上就掛了Orz

code:

#include<cstdio>
#include<map>
#include<vector>
#include<cassert>
using namespace std;
typedef long long LL;
int N,S[100000],DP[100000];
map<int,LL>ANS[100000];
LL GetCost(const int len,const int v)
{
    if(len==-1)return 0LL;
    auto it=ANS[len].lower_bound(v);
    assert(it!=ANS[len].begin());
    return (--it)->second;
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=0;i<N;i++)scanf("%d",&S[i]);
    for(int i=0;i<N;i++)ANS[i].clear();
    int len=0;
    for(int i=0;i<N;i++)
    {
        int l=0,r=len;
        while(l<r)
        {
            const int mid=(l+r)/2;
            if(DP[mid]<S[i])l=mid+1;
            else r=mid;
        }
        DP[r]=S[i];
        if(r==len)len++;
//        printf("i=%d,r=%d,len=%d\n",i,r,len);
        const LL cost=GetCost(r-1,S[i])+(i+1LL);
        auto it=ANS[r].upper_bound(S[i]);
        if(it==ANS[r].begin()||((--it)->second)>cost)
        {
            it=ANS[r].lower_bound(S[i]);
            vector<map<int,LL>::iterator>to_erase; 
            while(it!=ANS[r].end()&&(it->second)>=cost)to_erase.push_back(it++);
            for(const auto &v:to_erase)ANS[r].erase(v);
            ANS[r][S[i]]=cost;
        }
    }
//    printf("len=%d\n",len);
    auto it=ANS[len-1].end();it--;
    printf("%lld\n",it->second);
    return 0;
}