[POJ 3709][DP] K-Anonymous Sequence

原題連結
關於斜率優化想了解的可以看這篇。

本來想說WOW~~~經典斜率優化，穩穩水過~~
結果連續WA了快十次，最後崩潰上網找別人code，自產測資才發現原來是我斜率相同時的case判錯了。

而且這題其實根本不用特別判這case，你看code裡也沒寫(指

(如果你是用相除，也就是直接算交點座標的話或許會有需要......)

還有關於這題網路上的資源實在是太多了= ="
POJ討論區就有3篇題解，google一搜也是滿滿的解題報告，就不多說了。

#include<cassert>
#define LL long long
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
const LL maxn=500000+5;
struct Line
{
    LL slope,inter;
    LL getVal(LL x) {return slope*x+inter;}
}line[maxn];
LL a[maxn],pre[maxn],dp[maxn];
deque<Line> dq;
bool check(Line& L0,Line& L1,Line& L2)
{
    return (L0.inter-L2.inter)*(L1.slope-L0.slope)<=(L0.inter-L1.inter)*(L2.slope-L0.slope);
}
int main()
{
    LL T;
    scanf("%lld",&T);
    pre[0]=0;
    while(T--)
    {
        LL n,k;
        scanf("%lld%lld",&n,&k);
        for(LL i=1;i<=n;i++) {scanf("%lld",a+i);pre[i]=pre[i-1]+a[i];}
        dq.clear();
        line[1]=(Line){a[1],0};
        dq.push_back(line[1]);
        for(LL i=k;i<=n;i++)
        {
            while(dq.size()>=2 && dq[0].getVal(i)<=dq[1].getVal(i)) dq.pop_front();
            dp[i]=pre[i]-dq.front().getVal(i);
            line[i]=(Line){a[i],pre[i-1]+a[i]*(1LL-i)-dp[i-1]};
            if(i-k+2>=k+1)
            {
                while(dq.size()>=2 && check(dq[dq.size()-2],dq[dq.size()-1],line[i-k+2])) dq.pop_back();
                dq.push_back(line[i-k+2]);
            }
        }
        printf("%lld\n",dp[n]);
    }
}