思路
首先考虑暴力DP，我们预处理出从第 \(1\) 个点到第 \(n\) 个点木材重量、运输距离与运输费用的前缀和，枚举两个锯木厂的位置，设其分别在 \(i\) 点和 \(j\) 点。
易得状态转移方程为 $$ans=\min{f[j] \times (dis[j]-dis)+f \times dis-f \times dis[n+1]+g[n+1]\ }$$ 其中 \(f\) 表示木材重量，\(dis\) 表示距离，\(g\) 表示费用，时间复杂度 \(O(n^2)\)。
在P4360中，我们可以使用暴力DP水过该题，然而，加强数据后，明显TLE，考虑优化。
观察式子，我们分为只和 \(j\) 有关的，和 \(i\) 与 \(j\) 都有关的，只和 \(i\) 有关的三部分，可将其变形为 $$f[j] \times dis[j]=f[j] \times dis-f \times dis+f \times dis[n+1]+g[n+1]+ans$$ 对于该式子，可以进行斜率优化，我们想要使 \(-f \times dis+f \times dis[n+1]+g[n+1]+ans\) 最小，也就是令一次函数的截距最小，下凸包维护各点，用斜率 \(dis\) 查找即可，因为 \(dis\) 与 \(f\) 均递增，可用单调队列实现，复杂度 \(O(n)\) 十分优秀。
Code
[code]#include#define ll long long#define lb long doubleusing namespace std;const int M=1e5+10;int n,l;ll w[M],d[M];ll f[M],g[M],dis[M];ll dp[M];lb slope(int x,int y){ return (lb)((lb)f[y]*dis[y]-(lb)f[x]*dis[x])/(lb)((lb)f[y]-(lb)f[x]);}int h=1,t=0,q[M];int main(){ //memset(dp,0x7f,sizeof(dp)); ll ans=1e18+5; scanf("%d",&n); for(int i=1;i |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
