【鏈接】 鏈接
【題意】

在這里輸入題意

【題解】

設f[i]表示在第i個地方設立一個倉庫,且前面符合要求的最小花費。
則
\(f[i] = min(f[j] + c[i] + dis[i]*(sump[i] - sump[j])-(sumdp[i]-sumdp[j]));\)
其中
sump[]是p[]的前綴和,即\(sump[i] = p[1]+p[2]+..+p[i]\)
sumdp[]是x[]*p[]的前綴和,即\(sumdp[i] = x[1]*p[1]+x[2]*p[2]+...+x[i]*p[i]\)
這個表示j+1..i這一段的所有物品都運輸到i這個倉庫。
自己用筆寫一下就知道了。
顯然是個N^2算法。
斜率優化。
設x<y,且y優于x.
balabala就能得到
\(\frac{f[y]+sumdp[y]-(f[x]+sumdp[x])}{sump[y]-sump[x]}<dis[i]\)
又dis是單調遞增的。
這是一個經典的斜率優化問題了。

【錯的次數】

在這里輸入錯的次數

【反思】

在這里輸入反思

【代碼】

#include <bits/stdc++.h> #define ll long long using namespace std;const int N = 1e6;int n,dl[N+10],h,t; ll dis[N+10],p[N+10],c[N+10],sump[N+10],sumdp[N+10]; ll dp[N+10];double ju(int x,int y) {double fenzi = dp[y] + sumdp[y] - (dp[x]+sumdp[x]);double fenmu = sump[y] - sump[x];return fenzi/fenmu; }int main() {//freopen("F:\\rush.txt","r",stdin);scanf("%d",&n);for (int i = 1;i <= n;i++){scanf("%lld%lld%lld",&dis[i],&p[i],&c[i]);sump[i] = sump[i-1] + p[i];sumdp[i] = sumdp[i-1] + dis[i]*p[i];}for (int i = 1;i <= N;i++) dp[i] = 1e18;h = 1,t = 1;dl[1] = 0;for (int i = 1;i <= n;i++){while (h < t && ju(dl[h],dl[h+1])<dis[i]) h++;int j = dl[h];dp[i] = min(dp[i],dp[j] + c[i] +dis[i]*(sump[i]-sump[j])-(sumdp[i]-sumdp[j]));while (h < t && ju(dl[t-1],dl[t]) > ju(dl[t],i)) t--;dl[++t] = i;}printf("%lld\n",dp[n]);return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7637996.html

總結

以上是生活随笔為你收集整理的【BZOJ 1096】[ZJOI2007]仓库建设的全部內容，希望文章能夠幫你解決所遇到的問題。

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