推出来式子然后斜率优化水过去就完事了
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<vector>
- #include<queue>
- #include<cmath>
- #define inf 0x3f3f3f3f
- #define LL long long int
- using namespace std;
- const int maxn=50050;
- inline LL rd(){
- LL x=0;char c=getchar();int neg=1;
- while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
- while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
- return x*neg;
- }
- int N;
- LL co[maxn],sm[maxn],f[maxn],L;
- int q[maxn],h,t;
- inline LL pw2(LL x){return x*x;}
- inline bool judge1(int j1,int j2,int i){
- return f[j1]+pw2(j1+sm[j1])-f[j2]-pw2(j2+sm[j2])<(2*i+2*sm[i]-2*L-2)*(j1+sm[j1]-j2-sm[j2]);
- }
- inline bool judge2(int j1,int j2,int j3){
- return (f[j1]+pw2(j1+sm[j1])-f[j2]-pw2(j2+sm[j2]))*(j2+sm[j2]-j3-sm[j3])<
- (f[j2]+pw2(j2+sm[j2])-f[j3]-pw2(j3+sm[j3]))*(j1+sm[j1]-j2-sm[j2]);
- }
- int main(){
- int i,j,k;
- N=rd();L=rd();
- for(i=1;i<=N;i++)co[i]=rd(),sm[i]=sm[i-1]+co[i];
- h=t=1;q[1]=0;
- for(i=1;i<=N;i++){
- while(h<t&&!judge1(q[h],q[h+1],i)) h++;
- f[i]=f[q[h]]+pw2(i-q[h]-1+sm[i]-sm[q[h]]-L);
- while(h<t&&!judge2(q[t-1],q[t],i)) t--;
- q[++t]=i;
- }printf("%lld\n",f[N]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2722778.html