P3195

发表于 分类于
[HNOI2008]玩具装箱

[HNOI2008]玩具装箱

设 $pre(i)=\sum_{i=1}^{i}c_i$。

则秒出状态转移方程：

$$f(i)=\min_{j<i}{f(j)+(i-j-1-L+pre(i)-pre(j))^2}$$

然后写上就能拿到 20pts 的好成绩。

我们考虑把这个东西的 $i$ 与 $j$ 分离出来。

其实不化简也可以，但我们还是化简一下。

设 $x(i)=pre(i)+i$，$L’=L+1$ 然后原转移方程变成了：

$$f(i)=\min_{j<i}{f(j)+(x(i)-x(j)-L’)^2}$$

把只和 $i$ 有关的移项到左边，其余的都放在右边：

$$f(i)-(x(i)-L’)^2=\min_{j<i}{f(j)+x(j)^2+2x(j)(L’-x(i))}$$

我们把这个东西想象成一个 $b=y-kx$，让它变成一个固定 $k$，且使 $b$ 尽量最优的一个东西，于是只和 $i$ 有关的东西揉在一起变成 $b(i)$，只和 $j$ 有关的东西变成 $y(j)$，和 $i$ 与 $j$ 都有关的东西拆成 $-k(i)x(j)$ 的形式，所以 $k(i)=-2(L’-x(i))$，然后 $x(j)$ 就是 $x(j)$。

于是就变成了 $b(i)=y(j)-k(i)x(j)$，我们要找到一个点 $(x(p),y(p))$ 使得斜率为 $k(i)$ 的直线经过这个点时截距尽量小。

我们这个题性质比较好，所以考虑直接用单调队列来维护。

我们考虑维护一个下凸壳，这个斜线从下往上移动第一个碰到的点就是最优决策点。

显然满足前面一截线段的斜率小于等于 $k(i)$，后面一截大于 $k(i)$。

而最好的一点就是这个 $k(i)$ 是递增的，就是说我们的这个决策可以用单点队列维护。

最优决策点之前的点显然可以全部弹出。

最后把 $(x(i),y(i))$ 这个点加进去，显然把最后一截斜率大于新加该点斜率的点从队尾弹出（维护下凸壳和最优性）。

然后我们就 $O(n)$ 解决了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll __int128
using namespace std;

const ll N=5e4;

ll n,L;
ll c[N+5],pre[N+5],f[N+5],q[N+5];
ll x[N+5],y[N+5],k[N+5];

inline double Calc_Slope(ll a,ll b) {
  return (double)(y[b]-y[a])/(x[b]-x[a]);
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

int main() {
  
  n=read();L=read();L++;
  
  for(ll i=1;i<=n;i++) {
    c[i]=read();pre[i]=pre[i-1]+c[i];
    x[i]=pre[i]+i;k[i]=-2*(L-x[i]);
  }
  
  ll h=0,t=0;
  for(ll i=1;i<=n;i++) {
    while(h+1<=t&&Calc_Slope(q[h],q[h+1])<=k[i]) h++;
    f[i]=f[q[h]]+(x[i]-x[q[h]]-L)*(x[i]-x[q[h]]-L);
    y[i]=f[i]+x[i]*x[i];
    while(h+1<=t&&Calc_Slope(q[t],i)<=Calc_Slope(q[t-1],q[t])) t--;
    q[++t]=i;
  }
  
  write(f[n]);
  
  return 0;
}