题目
【题目描述】
K 理事长是占卜好手,他精通各种形式的占卜。今天,他要用正面写着 `I` ,背面写着 `O` 的卡片占卜一下日本 IOI 国家队的选手选择情况。
占卜的方法如下:
1. 首先,选取五个正整数 $A,B,C,D,E$;
2. 然后,拿出 $A+B+C+D+E$ 张卡片摆成一排,从左至右摆成 $A$ 张正面,$B$ 张反面,$C$ 张正面,$D$ 张反面,$E$ 张正面的形式。也就是说,从左到右依次摆 $A$ 张 `I`,$B$ 张 `O`,$C$ 张 `I`,$D$ 张 `O`,$E$ 张 `I`;
3. 再从预先确定的 $N$ 种操作中选择 $1$ 种以上,然后按照自己喜欢的顺序进行操作,同样的操作可以进行 $1$ 次及以上。第 $i$ 种操作是「把从左到右第 $L_i$ 张卡片到第 $R_i$ 张卡片(包括两端)翻过来」,因为需要用手操作,所以翻 $1$ 张牌需要花费 $1$ 秒,完成一次操作需要花费 $R_i-L_i+1$ 秒;
4. 操作后,如果所有牌都是正面朝上的,占卜就结束了。
因为这种占卜比较费时,所以 K 理事长在占卜之前想知道占卜能否结束,如果能结束,他想知道占卜的最小耗时。
【输入格式】
第一行,五个正整数 $A,B,C,D,E$,意义如题目描述;
第二行,一个正整数 $N$,意义如题目描述;
接下来 $N$ 行描述操作,一行两个正整数 $L_i,R_i$,意义如题目描述。
【输出格式】
输出一行,如果占卜能够结束,则输出一个正整数,表示占卜的最小耗时;如不能,输出 $-1$。
【样例输入一】
1 2 3 4 5
3
2 3
2 6
4 10
【样例输出一】
12
【样例解释一】
最初的卡片序列为 `IOOIIIOOOOIIIII`;
先进行第二个操作,卡片序列变为 `IIIOOOOOOOIIIII`,花费 $5$ 秒;
再进行第三个操作,卡片序列变为 `IIIIIIIIIIII`,这个操作花费 $7$ 秒,一共花费 $12$ 秒。
可以证明,$12$ 秒为占卜的最小耗时,因此输出 $12$。
【样例输入二】
1 1 1 1 1
1
1 1
【样例输出二】
-1
题解
考虑覆盖,从 $ i $ 覆盖到 $ j $ 相当于通过那些翻转,从 $ i $ 走到 $ j $(画图手动感知)
然后就变成了最短路,分别枚举起点和终点就可以了
(本题卡 int)
代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 #define LL long long 3 #define _(d) while(d(isdigit(ch=getchar()))) 4 using namespace std; 5 int R(){ 6 int x;bool f=1;char ch;_(!)if(ch=='-')f=0;x=ch^48; 7 _()x=(x<<3)+(x<<1)+(ch^48);return f?x:-x;} 8 const int N=5e5+5; 9 int n,a[6],head[N],cnt;LL dis[N],ans=2e18; 10 struct edge{int to,nex,w;}e[N<<1]; 11 struct node{ 12 int x;LL w; 13 bool friend operator <(node a,node b){return a.w>b.w;} 14 };priority_queue<node>q; 15 void add(int s,int t,int w){e[++cnt]=(edge){t,head[s],w},head[s]=cnt;} 16 void dij(int s){ 17 for(int i=0;i<=a[5];i++)dis[i]=2e18; 18 dis[s]=0; 19 q.push((node){s,0}); 20 while(!q.empty()){ 21 node now=q.top();q.pop(); 22 if(now.w!=dis[now.x])continue; 23 for(int v,k=head[now.x];k;k=e[k].nex) 24 if(dis[v=e[k].to]>dis[now.x]+e[k].w) 25 dis[v]=dis[now.x]+e[k].w,q.push((node){v,dis[v]}); 26 } 27 return; 28 } 29 int main(){ 30 for(int i=1;i<=5;i++)a[i]=a[i-1]+R(); 31 n=R(); 32 for(int i=1,u,v;i<=n;i++) 33 u=R()-1,v=R(),add(u,v,v-u),add(v,u,v-u); 34 dij(a[1]); 35 LL s1=dis[a[2]],s2=dis[a[3]],s3=dis[a[4]]; 36 dij(a[2]); 37 ans=min(min(ans,s2+dis[a[4]]),s3+dis[a[3]]); 38 dij(a[3]); 39 ans=min(ans,s1+dis[a[4]]); 40 printf("%lld ",ans==2e18?-1:ans); 41 return 0; 42 }