AT_joisc2015_d

如果你做过 CF79D 你就会把这题秒了。

记 $A+B+C+D+E=m$。

首先区间反转差分一下变成两个点同时反转，然后发现原序列差分序列上只有 $4$ 个 $1$，于是把反转转化成差分数组上 $1$ 的移动。

这是因为差分操作顺序不影响结果，所以每次操作的 $x,y$ 两个位置中，至少有一个 $1$ 才可能是最优的。

最后 $1$ 要不两个移动到同一位置然后相抵消，要不移动到 $m+1$，对原序列没有影响。

于是先预处理 $4$ 个开始的 $1$ 到所有位置的最短路，然后状压 dp 一下当前已经两两抵消的点集为 $S$，花费的最小的代价，再加上剩下点移动到 $m+1$ 的代价即可。

code：

int n,m,a[4];
bool vis[N];
ll f[4][4],dis[4][N],dp[1<<5];
int tot,head[N];
struct node{
	int to,nxt,cw;
}e[N<<1];
il void add(int u,int v,int w){
	e[++tot]={v,head[u],w},head[u]=tot;
}
void dij(int s,int p){
	priority_queue<pii> q;
	mems(vis,0);
	dis[p][s]=0,q.emplace(0,s);
	while(q.size()){
		int u=q.top().se;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		go(i,u){
			int v=e[i].to;
			if(dis[p][v]<=dis[p][u]+e[i].cw){
				continue;
			}
			dis[p][v]=dis[p][u]+e[i].cw;
			q.emplace(-dis[p][v],v);
		}
	}
}
void Yorushika(){
	int A,B,C,D,E;
	read(A,B,C,D,E,n),m=A+B+C+D+E;
	a[0]=A+1,a[1]=A+B+1,a[2]=A+B+C+1,a[3]=A+B+C+D+1;
	rep(i,1,n){
		int l,r;read(l,r);
		add(l,r+1,r-l+1),add(r+1,l,r-l+1);
	}
	mems(dis,0x3f),mems(f,0x3f),mems(dp,0x3f);
	rep(i,0,3){
		dij(a[i],i);
	}
	rep(i,0,3){
		rep(j,i+1,3){
			rep(k,1,m){
				f[i][j]=min(f[i][j],dis[i][k]+dis[j][k]);
			}
		}
	}
	ll ans=1ll*inf*inf;
	dp[0]=0;
	rep(S,0,15){
		rep(i,0,3){
			rep(j,i+1,3){
				if((S>>i&1)||(S>>j&1)){
					continue;
				}
				dp[S|(1<<i)|(1<<j)]=min(dp[S|(1<<i)|(1<<j)],dp[S]+f[i][j]);
			}
		}
		rep(i,0,3){
			if(S>>i&1){
				continue;
			}
			if(dis[i][m+1]>1e18){
				dp[S]=1ll*inf*inf;
			}else{
				dp[S]+=dis[i][m+1];
			}
		}
		ans=min(ans,dp[S]);
	}
	printf("%lld\n",ans>1e18?-1:ans);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}