AT F-Intervals 题解

简化题意：

有 $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;
} 

:::