为啥用双端队列(单调队列)不能先往队列里放一个0,难道不应该从0开始吗?
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dp[50011],c[50011],qzhc[50011];
ll LEN;int n;
ll K(int i){
return (qzhc[i]+i)*2;
}
ll X(int j){
return (qzhc[j]+j+LEN+1);
}
ll B(int i){
return dp[i]-(qzhc[i]+i)*(qzhc[i]+i);
}
ll Y(int j){
return dp[j]+(qzhc[j]+j+LEN+1)*(qzhc[j]+j+LEN+1);
}
long double Get_K(int p1,int p2){
return(Y(p2)-Y(p1))*1.0/(X(p2)-X(p1));
}
int deq[50011],head=1,tail=1;
int main(){
cin>>n>>LEN;
for(int i=1;i<=n;i++){
cin>>c[i];
qzhc[i]=qzhc[i-1]+c[i];
}
// dp[0]=0;deq[++tail]=0;去掉这里会出灵异的锅
for(int i=1;i<=n;i++){
while(head<tail&&
Get_K(deq[head],deq[head+1])<=K(i))head++;
dp[i]=dp[deq[head]]+
(i-deq[head]-1+qzhc[i]-qzhc[deq[head]]-LEN)*
(i-deq[head]-1+qzhc[i]-qzhc[deq[head]]-LEN);
while(head<tail&&
Get_K(i,deq[tail-1])<=Get_K(deq[tail-1],deq[tail]))tail--;
deq[++tail]=i;
}
cout<<dp[n];
return 0;
}