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