视频网站开发者工具,做网站有什么语言好,淘宝客网站主题下载,网站备案有什么好处理题意#xff1a;有 nnn 个柱子#xff0c;每个柱子有高度 hih_ihi。你需要在柱子间修桥#xff0c;在 i,ji,ji,j 间修桥代价为 (hi−hj)2(h_i-h_j)^2(hi−hj)2,桥梁只能在柱子处相交#xff0c;未安装桥的柱子需要拆除#xff0c;代价为 wiw_iwi#xff08;可能为…题意有 nnn 个柱子每个柱子有高度 hih_ihi。你需要在柱子间修桥在 i,ji,ji,j 间修桥代价为 (hi−hj)2(h_i-h_j)^2(hi−hj)2,桥梁只能在柱子处相交未安装桥的柱子需要拆除代价为 wiw_iwi可能为负数。求让 111 和 nnn 连接的最小代价。
n≤105,hi,∣wi∣≤106n\leq 10^5,h_i,|w_i|\leq 10^6n≤105,hi,∣wi∣≤106
显然是斜率优化
设 fif_ifi 表示从 111 修到 iii 的最小代价,sss 为 www 前缀和。
fimin1≤ji{fj(hi−hj)2si−1−sj}f_i\min_{1\leq ji}\{f_j(h_i-h_j)^2s_{i-1}-s_j\}fi1≤jimin{fj(hi−hj)2si−1−sj}
fimin1≤ji{fjhi2−2hihjhj2si−1−sj}f_i\min_{1\leq ji}\{f_jh^2_i-2h_ih_jh^2_js_{i-1}-s_j\}fi1≤jimin{fjhi2−2hihjhj2si−1−sj}
fihi2si−1min1≤ji{−2hj⋅hifjhj2−sj}f_ih^2_is_{i-1}\min_{1\leq ji}\{-2h_j\cdot h_if_jh_j^2-s_j\}fihi2si−11≤jimin{−2hj⋅hifjhj2−sj}
每个决策 jjj 看成斜率为 −2hj-2h_j−2hj,截距为 fjhj2−sjf_jh_j^2-s_jfjhj2−sj 的直线 hih_ihi 看成自变量李超线段树求最小值即可。
复杂度 O(nlogn)O(n\log n)O(nlogn)
#include iostream
#include cstdio
#include cstring
#include cctype
using namespace std;
const int N1e6,MAXNN5;
typedef long long ll;
inline int read()
{int ans0,f1;char cgetchar();while (!isdigit(c)) (c-)(f-1),cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return f*ans;
}
ll k[MAXN],b[MAXN];
inline ll calc(int i,int x){return k[i]*xb[i];}
#define lc p1
#define rc p1|1
int mn[MAXN2];
void modify(int p,int l,int r,int v)
{int mid(lr)1;if (!mn[p]) return (void)(mn[p]v);if (calc(mn[p],l)calc(v,l)calc(mn[p],r)calc(v,r)) return;if (calc(mn[p],l)calc(v,l)calc(mn[p],r)calc(v,r)) return (void)(mn[p]v);if (calc(mn[p],mid)calc(v,mid)) swap(mn[p],v);if (calc(mn[p],l)calc(v,l)) modify(lc,l,mid,v);else modify(rc,mid1,r,v);
}
void query(int p,int l,int r,int k,ll ans)
{if (mn[p]) ansmin(ans,calc(mn[p],k));if (lr) return;int mid(lr)1;if (kmid) query(lc,l,mid,k,ans);else query(rc,mid1,r,k,ans);
}
ll h[MAXN],s[MAXN],f[MAXN];
int main()
{int nread();for (int i1;in;i) h[i]read();for (int i1;in;i) s[i]s[i-1]read();k[1]-2*h[1],b[1]h[1]*h[1]-s[1];modify(1,0,N,1);for (int i2;in;i){query(1,0,N,h[i],f[i]1e18);f[i]h[i]*h[i]s[i-1];k[i]-2*h[i],b[i]h[i]*h[i]f[i]-s[i];modify(1,0,N,i);}coutf[n];return 0;
}
