2016年1月17日 星期日

[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;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原