分析：
首先先考虑300分做法：$dp[i][j]$表示前i个木板，第i个木板的左端点停在j处，转移的话就是$$dp[i][j] = dp[i-1][k] + |l[i]-j|,k \in [j-len_{i-1},j+len_i]$$
然后把dp[i]看作是关于j的函数，注意到这个函数是下凸包的。
$dp[1] = |l[1]-j|$显然是个下凸壳
然后发现dp[i]的计算操作相当于对于凸包斜率为负数的一段向左平移$len_i$，凸包斜率为正数的一段向右平移$len_{i-1}$，中间空出来的一段全取$0$。然后再和一个绝对值函数叠加，注意到下凸包+下凸包=下凸包，所以仍然是下凸包的
用两个单调队列维护下凸包，答案在凸包斜率为0的地方取
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 6 const int maxn = 102000; 7 8 ll l[maxn],r[maxn],len[maxn]; 9 priority_queue<ll,vector<ll>,greater<ll> > pq2; 10 priority_queue<ll,vector<ll>,less<ll> > pq1; 11 ll tot; 12 ll lf,rf; 13 14 int main(){ 15 ios::sync_with_stdio(false); 16 int n; 17 cin>>n; 18 for(int i=1;i<=n;i++){ 19 cin >> l[i] >> r[i]; 20 len[i] = r[i] - l[i]; 21 } 22 pq1.push(l[1]); pq2.push(l[1]); 23 // pq1 k less than 0 pq2 k greater than 0 24 // k is continuous in pq1 and pq2 25 for(int i=2;i<=n;i++){ 26 lf -= len[i]; 27 rf += len[i-1]; 28 if(l[i] >= pq1.top()+lf && l[i] <= pq2.top()+rf){ 29 pq1.push(l[i]-lf); pq2.push(l[i]-rf); 30 }else if(l[i] < pq1.top()+lf){ 31 pq2.push(pq1.top()+lf-rf); 32 pq1.push(l[i]-lf); pq1.push(l[i]-lf); 33 ll nb = pq1.top()+lf-l[i]; 34 tot += nb; 35 pq1.pop(); 36 }else{ 37 pq1.push(pq2.top()+rf-lf); 38 pq2.push(l[i]-rf); pq2.push(l[i]-rf); 39 ll nb = l[i]-rf-pq2.top(); 40 tot += nb; 41 pq2.pop(); 42 } 43 } 44 cout << tot <<endl; 45 return 0; 46 }