[bzoj1010]：[HNOI2008]玩具装箱toy

本文主要是介绍[bzoj1010]：[HNOI2008]玩具装箱toy，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
HNOI2008 All Clear!
这个题貌似有三种做法。。
首先可以斜率优化dp
然后可以证（da）明（biao）发现决策单调性
之后根据这个结论有两个做法：
1.每次算出来一个dp[i]，就往后二分查找影响区间的变化点x，然后将[x,n]涂上i
然后按照这样递推算出来就好了，涂色用线段树， $O(nlog^2n)$
2.用单调队列和二分查找，具体可以看hzwer的code
参（chao）考（xi）资料：http://hzwer.com/2114.html
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=5e4+5;
int n;
ll L,c[N],dp[N],sum[N];
struct data{int l,r,p;}q[N];
inline ll sq(ll x){return x*x;}
inline ll calc(int j,int i){return dp[j]+sq(sum[i]-sum[j]+i-j-1-L);}
inline int find(data t,int q){int l=t.l,r=t.r,mid;while(l<=r){mid=(l+r)>>1;if(calc(q,mid)<calc(t.p,mid))r=mid-1;else l=mid+1;}return l;
}
inline void DP(){int l=1,r=1;q[1]=(data){0,n,0};for(int i=1;i<=n;i++){if(i>q[l].r)l++;dp[i]=calc(q[l].p,i);if(l>r||calc(i,n)<calc(q[r].p,n)){while(l<=r&&calc(i,q[r].l)<calc(q[r].p,q[r].l))r--;if(l<=r){int t=find(q[r],i);q[r].r=t-1;q[++r]=(data){t,n,i};}else q[++r]=(data){i,n,i};}}
}
int main(){n=read();L=read();for(int i=1;i<=n;i++)c[i]=read();for(int i=1;i<=n;i++)sum[i]=sum[i-1]+c[i];DP();printf("%lld",dp[n]);return 0;
}