任务安排1~3：
模版。用到一个著名的思想：费用提前计算。
暴力维数高的原因是不能较快的知道前面分了几批
但是一旦分了一批，对后面都会有\(S\)的时间叠加
所以不妨设\(f_i\)表示已知会花费的时间min，
\(f_i = \min_{j=1}^{i-1} f_j + (SC_i-SC_j) \cdot ST_i + S \cdot (SC_n-SC_j)\)
\(O(n^2)\)通过T1.
大力拆式子，发现有一个叫做\(ST_i \cdot SC_j\)的玩意，i,j之间无法独立
不慌，还是先移项，得
\(f_j-SC_j \cdot S = ST_i \cdot SC_j + f_i - ST_i \cdot SC_i - S \cdot SC_n\)
\(i\)为常数，\(j\)为变量的话此为一次函数，维护下凸包即可
关于为何是下凸包：
1.直观理解：下面的截距才小，\(f_i\)才小
2.线性规划的结论证明
3.分类讨论证明
能理解就行
这样2、3都秒了，只是在单调队列中取哪个做答案的问题
其实还可以有4，\(T_i\)也能是负数
在凸包中间插点，set维护即可
B. Cats Transport
乍一看很难搞，两三个属性
分析一波，若feeder(\(t\)时刻出发)接到了一只cute cat，则它应该等待\(t+SD_i-T_i\)分钟（\(t \geq T_i -SD_i\)）
所以可设\(a_i = T_i - SD_i\)并排序
不难发现\(a\)小的cat应由出发早的人接
人少，可设\(f_{i,j}\)表示前\(i\)个人接走前\(j\)个cat最小时间
\(f_{i,j}=f_{i-1,k}+(j-k)*Sa_j-(Sa_j-Sa_k)\)
（贪心设置的t,无需多言)
\(i\)直接滚掉，移项得
\(pre_j + Sa_j = j \cdot Sa_i + f_i + (i-1) \cdot Sa_i\)
结束战斗
P3195 [HNOI2008]玩具装箱
套路了。。。
\(f_i\)表示前\(i\)个分好最小代价
设\(s_i = \sum_{j=1}^i c_j\)
\(f_i = f_j + (s_i-s_j+i-j-1-L)^2\)
设\(a_i=s_i+i\) , \(R = 1 - L\) , 则
\(f_i = f_j + (a_i - a_j + R)^2\),
化简即可不想写了
#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 100005
#define ll long long
int n,q[N],hh,tt;
ll f[N],s[N],D;
ll get_y(int j){return f[j]+(s[j]-D)*(s[j]-D);
}
int main(){scanf("%d%lld",&n,&D);D=-1ll-D;fr(i,1,n){scanf("%lld",&s[i]);s[i]+=s[i-1]; }fr(i,1,n)s[i]+=1ll*i;fr(i,1,n){while(hh<tt&&(get_y(q[hh+1])-get_y(q[hh]))<2ll*s[i]*(s[q[hh+1]]-s[q[hh]]))hh++;f[i]=f[q[hh]]+1ll*(s[i]-s[q[hh]]+D)*(s[i]-s[q[hh]]+D); while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(s[i]-s[q[tt]])>=(get_y(i)-get_y(q[tt]))*(s[q[tt]]-s[q[tt-1]]))tt--;q[++tt]=i;}printf("%lld\n",f[n]);return 0;
}
P2120 [ZJOI2007]仓库建设
\(f_i\)表示前\(i\)个的min
\(f_i = \min_{j=1}^{i-1} (f_j + c_i + x_i \cdot (Sp_i - Sp_j) - (Sxp_i - Sxp_j))\)
tips:其实不需要把整个式子拆开，只需观察出\(x\),\(y\),\(Slope\)即可
还是很好找的
注意此时钦定了\(n\)号位必建仓库，特判即可
#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 1000005
#define ll __int128
int n,q[N],hh,tt;
ll f[N],x[N],c[N],Sp[N],Sxp[N];
ll get_y(int j){return f[j]+Sxp[j];
}
int main(){scanf("%d",&n);int tmp,tmp1,tmp2,fl=0;fr(i,1,n){scanf("%d%d%d",&tmp1,&tmp,&tmp2);x[i]=tmp1,c[i]=tmp2;Sp[i]=Sp[i-1]+tmp;Sxp[i]=Sxp[i-1]+x[i]*tmp;if(i==n&&tmp==0)fl=1;}fr(i,1,n){while(hh<tt&&(get_y(q[hh+1])-get_y(q[hh]))<(Sp[q[hh+1]]-Sp[q[hh]])*x[i])hh++;f[i]=f[q[hh]]+c[i]+x[i]*(Sp[i]-Sp[q[hh]])-(Sxp[i]-Sxp[q[hh]]);while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(Sp[i]-Sp[q[tt]])>=(get_y(i)-get_y(q[tt]))*(Sp[q[tt]]-Sp[q[tt-1]]))tt--;q[++tt]=i;}printf("%lld\n",(long long)f[n]-fl*c[n]);return 0;
}
P3628 [APIO2010]特别行动队
一时竟分不清哪个是模版
\(f_i = f_j + A(s_i - s_j)^2+B(s_i-s_j) + C\)
《不难看出》,
\(y = f_j + As_j^2-Bs_j\) ,
\(x = s_j\) , \(Slope = 2As_i\)
舒服~
#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 1000005
#define ll long long
int n,q[N],hh,tt;
ll s[N],f[N],A,B,C;
ll get_y(int j){return f[j]+A*s[j]*s[j]-B*s[j];
}
int main(){scanf("%d%lld%lld%lld",&n,&A,&B,&C);ll x;fr(i,1,n){scanf("%lld",&x);s[i]=s[i-1]+x;}fr(i,1,n){while(hh<tt&&get_y(q[hh+1])-get_y(q[hh])>(s[q[hh+1]]-s[q[hh]])*2ll*A*s[i])hh++;int j=q[hh];f[i]=f[j]+A*(s[i]-s[j])*(s[i]-s[j])+B*(s[i]-s[j])+C;while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(s[i]-s[q[tt]])<=(get_y(i)-get_y(q[tt]))*(s[q[tt]]-s[q[tt-1]]))tt--;q[++tt]=i;}printf("%lld\n",f[n]);return 0;
}
P4360 [CEOI2004]锯木厂选址
可以看出考虑\(f_i\)表示\(i\)处已经有一个兜底，还能再建一个，运完前\(i\)个最小代价
则\(f_i\)
\(= \min_{j=1}^{i-1}(\sum_{k=1}^j(x_j-x_k) \cdot p_k+\sum_{k=j+1}^i(x_i-x_k) \cdot p_k)\)
\(= x_j\sum_{k=1}^j p_k+x_i\sum_{k=j+1}^i p_k -\sum_{k=1}^i x_k \cdot p_k\)
\(= x_j \cdot Sp_j + x_i \cdot Sp_i - x_i \cdot Sp_j - Sxp_i\)
整理得
\(x_j \cdot Sp_j = x_i \cdot Sp_j + f_i - x_i \cdot Sp_i + Sxp_i\)
没有\(f_j\)好害怕
一样嘛，就是把只有\(j\)的全移到左边当\(y\)，\(ij\)乘积项当\(x\)，其余截距，这是精髓
求出\(f_i\)，\(ans = \min_{i=1}^n (f_i + \sum_{j=i+1}^n(x_{n+1}-x_j) \cdot p_j)\)
小发现：\(\sum x \cdot p\)可以最后一起算
#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 20005
#define ll long long
int n,q[N],hh,tt;
ll ans=1e18,f[N],x[N],p[N],res;
ll get_y(int j){return x[j]*p[j];
}
int main(){scanf("%d",&n);ll tmp;fr(i,1,n){scanf("%lld%lld",&p[i],&tmp);res+=x[i]*p[i];p[i]+=p[i-1];x[i+1]=x[i]+tmp;}fr(i,1,n){while(hh<tt&&get_y(q[hh+1])-get_y(q[hh])<(p[q[hh+1]]-p[q[hh]])*x[i])hh++;f[i]=x[i]*p[i]+p[q[hh]]*(x[q[hh]]-x[i]);while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(p[i]-p[q[tt]])>(get_y(i)-get_y(q[tt]))*(p[q[tt]]-p[q[tt-1]]))tt--;q[++tt]=i;ans=min(ans,f[i]+x[n+1]*(p[n]-p[i]));}printf("%lld\n",ans-res);return 0;
}
完结撒电脑
