玩具裝箱

luogu 3195

題目大意

有n件物品，每件物品有相對的長度$C_i$現在要把這n件物品放到容器中，切放的物品必須是連續的，若把第i件物品到第j件物品放到一個容器中，那此容器的長度定義為$x=j?i+{\sum }_{k=i}^j{C}_i$，此容器的費用即為$(x?L{)}^2$（L是常數），現在問你把所有物品放倒容器中，費用之和最小是多少

輸入樣例

5 4 3 4 2 1 4

輸出樣例

1

數據范圍

對于全部的測試點，$1\le n\le 5\times 10^4$，$1\le L\le 10^7$，$1\le C_i\le 10^7$。

解題思路

我們設f[i]為把1至i的所有物品放進容器中的最小費用，那我們可以得出轉移方程：
$$f_i=f_j+(i?(j+1)+su{m}_i?su{m}_j?L{)}^2$$
注：sum是C的前綴和，這個范圍是j+1到i所以減的是j+1，前綴和減的是sum[(j+1)-1]
但是會超時間，所以我們要考慮優化
我們可以變式為：
$$f_i=f_j+((i+su{m}_i?1?L)?(j+su{m}_j){)}^2$$
然后把平方拆開，得到：
$$f_i=f_j+(i+su{m}_i?1?L{)}^2?2?(i+su{m}_i?1?L)?(j+su{m}_j)+(j+su{m}_j{)}^2$$
若有決策點a,b滿足a>b且a比b優
則
$$f_a+(i+su{m}_i?1?L{)}^2?2?(i+su{m}_i?1?L)?(a+su{m}_a)+(a+su{m}_a{)}^2<f_j+(i+su{m}_i?1?L{)}^2?2?(i+su{m}_i?1?L)?(b+su{m}_b)+(b+su{m}_b{)}^2$$
變式
$$f_a?2?(i+su{m}_i?1?L)?(a+su{m}_a)+(a+su{m}_a{)}^2<f_j?2?(i+su{m}_i?1?L)?(b+su{m}_b)+(b+su{m}_b{)}^2$$
$$(f_a+(a+su{m}_a{)}^2)?(f_b+(b+su{m}_b{)}^2)<2?(i+su{m}_i?1?L)?((a+su{m}_a)?(b+su{m}_b))$$
$$((f_a+(a+su{m}_a{)}^2)?(f_b+(b+su{m}_b{)}^2))/((a+su{m}_a)?(b+su{m}_b))<2?(i+su{m}_i?1?L)$$
設
$x_i=i+su{m}_i$
$y_i=f_i+(i+su{m}_i{)}^2$
則
$(y_a?y_b)/(x_a?x_b)<2?(i+su{m}_i?1?L)$
帶入模板即可

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n, L, l, r, a[50010], sum[50010], x[50010], y[50010], q[50010], f[50010]; int main() {scanf("%lld %lld", &n, &L);for (ll i = 1; i <= n; ++i){scanf("%lld", &a[i]);sum[i] = sum[i - 1] + a[i];x[i] = sum[i] + i;}memset(f, 127/3, sizeof(f));f[0] = 0;q[1] = 0;l = 1;r = 1;for (ll i = 1; i <= n; ++i){while(l < r && (y[q[l + 1]] - y[q[l]]) <= 2 * (x[i] - 1 - L) * (x[q[l + 1]] - x[q[l]]))l++;//模板f[i] = f[q[l]] + (x[i] - x[q[l]] - 1 - L) * (x[i] - x[q[l]] - 1 - L);y[i] = f[i] + x[i] * x[i];while(l < r && (y[q[r]] - y[q[r - 1]]) * (x[i] - x[q[r]]) >= (y[i] - y[q[r]]) * (x[q[r]] - x[q[r - 1]])) r--;q[++r] = i;}printf("%lld", f[n]);return 0; }

總結

以上是生活随笔為你收集整理的【斜率优化】玩具装箱（luogu 3195）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。