T1.P3195 [HNOI2008]玩具装箱
-
斜率优化 \(\mathtt{DP}\) 板题；
虽然这是板题但签到题就是紫的是否有些过分？ -
朴素 \(DP\) 式子：\(f_i=\min\limits_{j=1}^{i-1}\{f_i,f_j+(sum_i-sum_j+i-j-L)^2\}\)，\(sum\) 是长度的前缀和。这里为了方便处理，先把所有长度以及 \(L+1\)，这样后面的平方里面就可以化简为 \(sum_i-sum_j-L\)。
-
转化：\(f_i=f_j+sum_i^2+sum_j^2+L^2-2sum_i sum_j-2sum_i L+2sum_j L\)，
把含 \(i\) 项视作常数，然后与 \(k\) 相减得 \(f_j-f_k+sum_j^2-sum_k^2-2sum_i sum_j+2sum_i sum_k+2sum_j L-2sum_k L=0\)
于是设 \(y_i=f_i+sum_i^2\)，\(x_i=sum_i\)，
于是斜率 \(=\frac{y_j-y_k}{x_j-x_k}\)，需要与 \(2sum_i-2L\) 比较。
AC code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=5e4+10;
int n,L;
ll c[N];
ll f[N];
int q[N],l,r;
#define y(i) (f[i]+c[i]*c[i])
double g(int a,int b){
return (double)(y(a)-y(b))/(double)(c[a]-c[b]);
}
int main(){
n=read(),L=read()+1;
for(int i=1;i<=n;++i)
c[i]=read()+1;
for(int i=1;i<=n;++i)
c[i]+=c[i-1];
l=r=1;
for(int i=1;i<=n;++i){
while(l<r && g(q[l],q[l+1])<0ll+1ll*2*c[i]-1ll*2*L)
++l;
f[i]=f[q[l]]+1ll*(0ll+L-c[i]+c[q[l]])*(0ll+L-c[i]+c[q[l]]);
// cerr<<i<<" "<<q[l]<<endl;
while(l<r && g(q[r-1],q[r])>=g(q[r],i))
--r;
q[++r]=i;
}
printf("%lld",f[n]);
return 0;
}
/*
5 4
3
4
2
1
4
*/