簡化題意：

有 $n$ 個區間，保證所有區間同時覆蓋一個點，每次將區間平移一個單位，問使得區間兩兩不交的最小操作數（端點處可重疊）。$n\le 5000。l,r\le 2^{31}?1$。

思路：

答案區間一定是連續的一段。而且最優的情況一定是中間的區間不動，一半移向左，一半移向右。對于 $n$ 為偶數的情況，選任意一個均可或新增一個$(p,p)$ 區間。
先將區間按照長度從大到小排序。
不用枚舉這個中間的區間，我們設 $f_{i,j,0/1}$ 表示前 $i$ 個區間中 $j$ 個向左移動，沒選/選了中間的區間。
對于轉移，我們分別轉移到向左，向右和中間三個狀態。
向左舉例：$f_{i+1,j+1,k}=min(f_{i+1,j+1,k},f_{i,j,k}+a_i.r+a_i.len\times j)$。因為所有比它大的都要經過它，還需移動 $a[i].r$ 使整個區間與左側區間不交。
注意雖然本題 $n$ 為 $5000$，但向左的最多只會有一半，所以第二維開到一般即可，要不然容易MLE。
:::info[code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5005;
int n;
int L,R;
struct node{ll l,r,len;
}q[N]; 
ll f[N][N][2];
bool cmp(node x,node y){
//	if(x.len==y.len) return x.l<y.l;return x.len>y.len;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&q[i].l,&q[i].r);//	q[i].l=-q[i].l; q[i].len=q[i].r-q[i].l;//點可重 }sort(q+1,q+1+n,cmp);memset(f,0x3f,sizeof f);L=n/2,R=(n-1)/2;f[0][0][0]=0;for(int i=0;i<n;i++){for(int j=0;j<=L;j++){//	if(i-j<0||i-j>R) continue;if(i-j>=0&&i-j<=R)f[i+1][j][1]=min(f[i+1][j][1],f[i][j][0]-q[i+1].l*L+q[i+1].r*R);if(j+1<=L){if(i-j-1>=0&&i-j-1<=R) f[i+1][j+1][1]=min(f[i+1][j+1][1],f[i][j][1]+q[i+1].r+q[i+1].len*j);if(i-j>=0&&i-j<=R)f[i+1][j+1][0]=min(f[i+1][j+1][0],f[i][j][0]+q[i+1].r+q[i+1].len*j);				}if(i-j<=R){if(i-j-1>=0&&i-j-1<=R) f[i+1][j][1]=min(f[i+1][j][1],f[i][j][1]-q[i+1].l+q[i+1].len*(i-j-1));}if(i-j+1<=R){if(i-j>=0&&i-j<=R)f[i+1][j][0]=min(f[i+1][j][0],f[i][j][0]-q[i+1].l+q[i+1].len*(i-j));}//	cout<<i<<" "<<j<<" "<<0<<" "<<f[i][j][0]<<endl; //	cout<<i<<" "<<j<<" "<<1<<" "<<f[i][j][1]<<endl; }}printf("%lld\n",f[n][L][1]);return 0;
} 

:::