题目传送门
题目描述
给出 \(n\)、\(m\) 和序列 \(c\)。
可以分多行，一行如果要打印 \(l\) 到 \(r\) 的单词，代价是 \(m+\left(\sum_{i=l}^{r}c_i\right)^2\)。
求最小代价和。
第一步肯定是把 \(c\) 做一遍前缀和。
朴素 \(O(n^2)\) dp：
\[dp_i=\min_{0\le j<i}dp_j+(c_i-c_j)^2+m
\]
把它斜率优化。
\[dp_i=\min_{0\le j<i}dp_j+c_i^2-2c_ic_j+c_j^2+m
\]
当 \(k>j\) 但决策 \(k\) 比决策 \(j\) 更优时：
\[\begin{aligned}
dp_j+c_i^2-2c_ic_j+c_j^2+m&>dp_k+c_i^2-2c_ic_k+c_k^2+m\\
dp_j-2c_ic_j+c_j^2&>dp_k-2c_ic_k+c_k^2\\
2c_i(c_k-c_j)&>(dp_k+c_k^2)-(dp_j+c_j^2)\\
2c_i&>\frac{(dp_k+c_k^2)-(dp_j+c_j^2)}{c_k-c_j}
\end{aligned}
\]
因为 \(2c_i\) 递增，所以直接用单调队列维护就行。
感觉和这个一模一样。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=5e5+5;
int n,m;
int que[N],h,t;
ll a[N],dp[N];
ll Y(int x){return dp[x]+a[x]*a[x];}
ll X(int x){return a[x];}
bool le(int x,int y,ll k){ll dy=Y(y)-Y(x);ll dx=X(y)-X(x);return dy <= k*dx;
}
bool ge(int x1,int x2,int x3){ll dy1=Y(x2)-Y(x1),dx1=X(x2)-X(x1);ll dy2=Y(x3)-Y(x2),dx2=X(x3)-X(x2);return dy1*dx2>=dy2*dx1;
}
ld slope(int x,int y){return (Y(y)-Y(x))*1.0/(X(y)-X(x));}
int main(){while(~scanf("%d %d",&n,&m)){memset(dp,0x3f,sizeof dp);dp[0]=0;for(int i=1;i<=n;++i) scanf("%lld",a+i),a[i]+=a[i-1];que[h=t=1]=0;for(int i=1;i<=n;++i){while(h<t&&le(que[h],que[h+1],2*a[i])) ++h;int j=que[h];dp[i]=dp[j]+(a[i]-a[j])*(a[i]-a[j])+m;while(h<t&&ge(que[t-1],que[t],i)) --t;que[++t]=i;}printf("%lld\n",dp[n]);}
}