【题目链接】
ybt 1610：玩具装箱
洛谷 P3195 [HNOI2008] 玩具装箱
【题目考点】
1. 动态规划：斜率优化动规
斜率优化动规模板题：信息学奥赛一本通 1607：【 例 2】任务安排 2 | 洛谷 P10979 任务安排 2
【解题思路】
玩具长度 C C C序列是由n个整数构成的整数序列。每个容器中放入的玩具是 C C C序列的一个子段。
该问题抽象后为：给定整数序列 C C C，将该序列分为若干个子段，子段[l, r]的费用为 ( r − l + ∑ i = l r C i − L ) 2 (r-l+\sum_{i=l}^rC_i-L)^2 (r−l+∑i=lrCi−L)2。对于所有的子段划分方案，求所有子段费用加和最小的方案的费用加和。
1. 状态定义
- 阶段：前i个元素
- 决策：确定一个子段
- 策略：子段划分方案
- 策略集合：前i个元素的所有子段划分方案
- 条件：费用加和最小
- 统计量：费用加和
状态定义 d p i dp_i dpi：前i个元素的所有子段划分方案中，费用加和最小的方案的费用加和。
初始状态 d p 0 dp_0 dp0：前0个元素的费用加和为0。
2. 状态转移方程
- 策略集合：前i个元素的所有子段划分方案
- 分割策略集合：最后一个子段的起始位置划分策略集合
设序列 C C C的前缀和数组为 s u m C sumC sumC，则子段 [ l , r ] [l, r] [l,r]的费用为 ( r − l + ∑ i = l r C i − L ) 2 = ( r − l + s u m C r − s u m C l − 1 − L ) 2 (r-l+\sum_{i=l}^rC_i-L)^2 = (r-l+sumC_r-sumC_{l-1}-L)^2 (r−l+∑i=lrCi−L)2=(r−l+sumCr−sumCl−1−L)2
前i个元素进行子段划分，设最后一个子段为 [ j + 1 , i ] [j+1, i] [j+1,i]。
显然j最小为0，整个序列就是最后一个子段。j最大为i-1，此时最后一个子段只有第i元素。j的范围为 0 ≤ j < i 0\le j < i 0≤j<i
前i个元素的费用加和，为前j个元素进行子段划分的最小费用加和 d p j dp_j dpj加上最后一个子段的费用 ( i − j − 1 + s u m C i − s u m C j − L ) 2 (i-j-1+sumC_i-sumC_j-L)^2 (i−j−1+sumCi−sumCj−L)2。取所有费用加和的最小值
因此状态转移方程为： d p i = m i n { d p j + ( i − j − 1 + s u m C i − s u m C j − L ) 2 } , 0 ≤ j < i dp_i = min\{dp_j+(i-j-1+sumC_i-sumC_j-L)^2\}, 0\le j < i dpi=min{dpj+(i−j−1+sumCi−sumCj−L)2},0≤j<i
设 S i = s u m C i + i = ∑ j = 1 i C j + i = ∑ j = 1 i ( C j + 1 ) S_i = sumC_i+i = \sum_{j=1}^iC_j+i=\sum_{j=1}^i(C_j+1) Si=sumCi+i=∑j=1iCj+i=∑j=1i(Cj+1)，因此 S i S_i Si就是 C i + 1 C_i+1 Ci+1的前缀和。
使 L ′ = L + 1 L'=L+1 L′=L+1，去掉状态转移方程中的min，方程写为：
d p i = d p j + ( S i − S j − L ′ ) 2 dp_i = dp_j+(S_i-S_j-L')^2 dpi=dpj+(Si−Sj−L′)2
将与j相关的量视为变量，整理为
d p i = d p j + ( S i − L ′ ) 2 + S j 2 − 2 ( S i − L ′ ) S j dp_i = dp_j+(S_i-L')^2+S_j^2-2(S_i-L')S_j dpi=dpj+(Si−L′)2+Sj2−2(Si−L′)Sj
d p j + S j 2 = 2 ( S i − L ′ ) S j + d p i − ( S i − L ′ ) 2 dp_j+S_j^2=2(S_i-L')S_j+dp_i-(S_i-L')^2 dpj+Sj2=2(Si−L′)Sj+dpi−(Si−L′)2
设 y = d p j + S j 2 y = dp_j+S_j^2 y=dpj+Sj2， x = S j x=S_j x=Sj， k = 2 ( S i − L ′ ) k=2(S_i-L') k=2(Si−L′)， b = d p i − ( S i − L ′ ) 2 b = dp_i-(S_i-L')^2 b=dpi−(Si−L′)2，上式可以写为 y = k x + b y=kx+b y=kx+b
其实这里整理成 d p j + S j 2 + 2 L ′ S j = 2 S i S j + d p i − ( S i − L ′ ) 2 dp_j+S_j^2+2L'S_j=2S_iS_j+dp_i-(S_i-L')^2 dpj+Sj2+2L′Sj=2SiSj+dpi−(Si−L′)2也可以求解。
只要保证：y、x是只与j相关的表达式，k是与i相关的表达式，b中有 d p i dp_i dpi即可
对于 0 ≤ j < i 0\le j < i 0≤j<i的所有决策点 ( x , y ) (x, y) (x,y)即 ( S j , d p j + S j 2 ) (S_j, dp_j+S_j^2) (Sj,dpj+Sj2)，看过哪一个决策点的斜率为 k k k的直线的截距 b b b是最小的，此时求出的就是 d p i dp_i dpi的最小值。
接下来进行斜率优化，本文只进行大体描述，具体细节见：
信息学奥赛一本通 1607：【 例 2】任务安排 2 | 洛谷 P10979 任务安排 2
设单调队列q维护所有的决策点集合中的下凸壳。q的队头为 q l q_l ql，队尾为 q r q_r qr
此时随着i的增大， k = 2 ( S i − L ′ ) k=2(S_i-L') k=2(Si−L′)是增大的，因此对于所有 q l q_l ql到 q l + 1 q_{l+1} ql+1的斜率 K ( q l , q l + 1 ) K(q_l, q_{l+1}) K(ql,ql+1)满足 K ( q l , q l + 1 ) ≤ 2 ( S i − L ′ ) K(q_l, q_{l+1})\le 2(S_i-L') K(ql,ql+1)≤2(Si−L′)的 q l q_l ql可以进行队头出队。
而后取当前的队头 q l q_l ql作为最优决策点，将 j = q l j=q_l j=ql带入 d p i = d p j + ( S i − S j − L ′ ) 2 dp_i = dp_j+(S_i-S_j-L')^2 dpi=dpj+(Si−Sj−L′)2，求出 d p i dp_i dpi，新的决策点为 ( S i , d p i + S i 2 ) (S_i, dp_i+S_i^2) (Si,dpi+Si2)。
维护下凸壳，保证没有上凸点，只要 K ( q r , i ) ≤ K ( q r − 1 , q r ) K(q_r, i) \le K(q_{r-1}, q_r) K(qr,i)≤K(qr−1,qr)，那么队尾入队i。
最后输出 d p n dp_n dpn
【题解代码】
解法1：斜率优化
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 50005
LL n, L, c[N], s[N], dp[N];//dp[i]：：前i个元素的所有子段划分方案中，费用加和最小的方案的费用加和。
int q[N], l = 1, r = 0;//单调队列
LL Y(int j)
{
return dp[j]+s[j]*s[j];
}
LL X(int j)
{
return s[j];
}
LL K(int i)
{
return 2*(s[i]-L);
}
bool cmp(LL a1, LL b1, LL a2, LL b2)//a1/b1 <= a2/b2
{
return a1*b2 <= a2*b1;
}
int main()
{
cin >> n >> L;
L++;//L'= L+1
for(int i = 1; i <= n; ++i)
{
cin >> c[i];
s[i] = s[i-1]+c[i]+1;
}
q[++r] = 0;//dp[0] = 0，添加决策点(s[0], dp[0]+s[0]^2)
for(int i = 1; i <= n; ++i)
{
while(l < r && cmp(Y(q[l+1])-Y(q[l]), X(q[l+1])-X(q[l]), K(i), 1))
l++;
dp[i] = dp[q[l]]+(s[i]-s[q[l]]-L)*(s[i]-s[q[l]]-L);
while(l < r && cmp(Y(i)-Y(q[r]), X(i)-X(q[r]), Y(q[r])-Y(q[r-1]), X(q[r])-X(q[r-1])))
r--;
q[++r] = i;
}
cout << dp[n];
return 0;
}