[POJ 3709]K-Anonymous Sequence

說明：
$S_{i}$為序列中第$i$個元素
$SUM_{i}$為$\sum_{k=1}^{i}S_{k}$

我們先來設計一個的$DP$，$DP[i]$代表$S_{1}\sim S_{i}$這個序列要符合$k$-anonymous，cost最小多少

起始狀態：
$DP[0]=0$
$DP[i]=INF$ ($1\leq i<K$)

然後，我們有了以下遞迴式：
$DP[i]=\min(DP[k]+(SUM_{i}-SUM_{k})-S_{k+1}*(i-k))$，$0\leq k\leq i-K$ (注意$k$的大小寫)

整理一下就變成這樣：
$DP[i]=\min((-S_{k+1})*i+(DP[k]-SUM_{k}+S_{k+1}*k)+(SUM_{i}))$

就會變成一條條斜率$(-S_{k+1})$，截距$(DP[k]-SUM_{k}+S_{k+1}*k)$的直線中找$x=i$時的最小值

如果$k$的範圍是$0\sim i-1$的話，相信大家知道怎麼用凸包優化的單調隊列來解

但是現在我們限制$k\leq i-K$
怎麼辦呢？

當要計算$DP_{i}$的時候，我們只需維護好範圍$0\sim i-K$的凸包就好了

給大家一個圖片想像，這個凸包會長得類似圖片中的紅線：

時間複雜度：$O(N)$

code:

#include<cstdio>
#include<cassert>
using namespace std;
typedef long long LL;
const LL INF=500000LL*500000LL+1LL;
struct Deq
{
    int s[500001],l,r;
    void clear(){l=0,r=-1;}
    void push_back(const int v){s[++r]=v;}
    void pop_back(){r--;}
    void pop_front(){l++;}
    int back(const int i)const{return s[r-i];}
    int front(const int i)const{return s[l+i];}
    int size()const{return r-l+1;}
    bool empty()const{return r<l;}
    void Print()const{for(int i=l;i<=r;i++)printf("%d ",s[i]);puts("");}
}DEQ;
int N,K,S[500001];
LL SUM[500001],DP[500002];
LL GetA(const int i){return -S[i+1];}
LL GetB(const int i){return (LL)S[i+1]*i+DP[i]-SUM[i];}
double GetX(const int i1,const int i2){assert(GetA(i1)!=GetA(i2));return (double)(GetB(i1)-GetB(i2))/(GetA(i2)-GetA(i1));}
bool NeedPopBack(const int i)
{
    if(DEQ.empty())return false;
    else if(GetA(DEQ.back(0))==GetA(i))return GetB(i)<=GetB(DEQ.back(0));
    else if(DEQ.size()==1)return false;
    else return GetX(DEQ.back(0),i)<=GetX(DEQ.back(1),DEQ.back(0));
}
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d",&N,&K);
        S[0]=SUM[0]=0LL;
        for(int i=1;i<=N;i++)scanf("%d",&S[i]);
        for(int i=1;i<=N;i++)SUM[i]=SUM[i-1]+S[i];
        //DP[i]=min(DP[k]+(SUM[i]-SUM[k])-S[k+1]*(i-k))
        //=DP[k]+SUM[i]-SUM[k]-S[k+1]*i+S[k+1]*k
        //=-S[k+1]*i+S[k+1]*k+DP[k]-SUM[k]+SUM[i]
        DP[0]=0LL;
        for(int i=1;i<K;i++)DP[i]=INF;
        DEQ.clear();
        for(int i=0;i<=N-K;i++)
        {
            while(NeedPopBack(i))DEQ.pop_back();
            if(DEQ.empty()||GetA(DEQ.back(0))!=GetA(i))DEQ.push_back(i);
            while(DEQ.size()>=2&&GetX(DEQ.front(0),DEQ.front(1))<=(double)i+K)DEQ.pop_front();
            const int k=DEQ.front(0);
            DP[i+K]=GetA(k)*(i+K)+GetB(k)+SUM[i+K];
//            printf("DP[%d]=%lld\n",i+K,DP[i+K]);
//            printf("i=%d: ",i),DEQ.Print();
        }
        printf("%I64d\n",DP[N]);
    }
    return 0;
}