Category Archives: DefaultCategory

ZOJ 1576(稳定婚姻系统-重名)

Posted on by
Marriage is Stable

Time Limit: 5 Seconds
Memory Limit: 32768 KB Special Judge

Albert, Brad, Chuck are happy bachelors who are in love with Laura, Marcy, Nancy. They all have three choices. But in fact, they do have some preference in mind. Say Albert, he likes Laura best, but that doesn't necesarily mean Laura likes him. Laura likes
Chuck more than Albert. So if Albert can't marry Laura, he thinks Nancy a sensible choice. For Albert, he orders the girls Laura > Nancy > Marcy.

For the boys:

Albert: Laura > Nancy > Marcy
Brad: Marcy > Nancy > Laura
Chuck: Laura > Marcy > Nancy

For the girls:

Laura: Chuck > Albert > Brad
Marcy: Albert > Chuck > Brad
Nancy: Brad > Albert > Chuck

But if they were matched randomly, such as

Albert <-> Laura
Brad <-> Marcy
Chuck <-> Nancy

they would soon discover it's not a nice solution. For Laura, she likes Chuck instead of Albert. And what's more, Chuck likes Laura better than Nancy. So Laura and Chuck are likely to come together, leaving poor Albert and Nancy.

Now it's your turn to find a stable marriage. A stable marriage means for any boy G and girl M, with their choice m[G] and m[M], it will not happen that rank(G, M) < rank(G, m[G]��and rank(M, G) < rank(M, m[M]).

Input

Each case starts with an integer n (1 <= n <= 500), the number of matches to make.

The following n lines contain n + 1 names each, the first being name of the boy, and rest being the rank of the girls.

The following n lines are the same information for the girls.

Process to the end of file.

Output

If there is a stable marriage, print n lines with two names on each line. You can choose any one if there are multiple solution. Print "Impossible" otherwise.

Print a blank line after each test.

Sample Input

3
Albert Laura Nancy Marcy
Brad Marcy Nancy Laura
Chuck Laura Marcy Nancy
Laura Chuck Albert Brad
Marcy Albert Chuck Brad
Nancy Brad Albert Chuck

Sample Output

Albert Nancy
Brad Marcy
Chuck Laura

这题就是稳定婚姻系统，

注意有同名的男女。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<queue>
#include<iostream>
#include<map>
#include<string>
using namespace std;
#define MAXN (2000+10)
int n;
queue<int> q;
map<string,int> hpos_male,hpos_female;

int female_like[MAXN][MAXN];  //SIS
int male_like[MAXN][MAXN];    //SSI
int match[MAXN];
string a[MAXN];
int main()
{
//	freopen("zoj1576.in","r",stdin);
	while (scanf("%d",&n)!=EOF)
	{
		hpos_male.clear();
		hpos_female.clear();
		memset(match,0,sizeof(match));
		int size=n+1;
		for (int i=1;i<=n;i++)
		{
			cin>>a[i];hpos_male[a[i]]=i; q.push(i);
			for (int j=1;j<=n;j++)
			{
				string s;
				cin>>s;
				if (i==1)
				{
					hpos_female[s]=size;
					a[size]=s;
					size++;
				}
				male_like[i][j]=hpos_female[s];
			}
		}
		for (int i=n+1;i<=2*n;i++)
		{
			string sg;
			cin>>sg;
			for (int j=1;j<=n;j++)
			{
				string s;
				cin>>s;
				female_like[hpos_female[sg]][hpos_male[s]]=j;
			}
		}
		/*
		for (int i=n+1;i<=2*n;i++)
		{
			for (int j=1;j<=n;j++)
				cout<<female_like[make_pair(a[i],a[j])]<<' ';
			cout<<endl;
		}
		*/
		while (!q.empty())
		{
			int now=q.front();
			q.pop();
			for (int j=1;j<=n;j++)
			{
				int v=male_like[now][j];
				if (!match[v])
				{
					match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
					break;
				}
				else if (female_like[v][match[v]]>female_like[v][now])
				{
					q.push(match[v]);
					match[match[v]]=0;
					match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
					break;
				}
			}
		}
		for (int i=1;i<=n;i++)
		{
			cout<<a[i]<<' '<<a[match[i]]<<endl;
		}
		printf("n");
	}
	return 0;
}


Tyvj P2079(Spfa)

Posted on by

P2079 - 防御机制

From tangjz    Normal (OI)
总时限：10s    内存限制：128MB    代码长度限制：64KB

背景 Background

NOIp2012考后欢乐赛第三题

描述 Description

　　服务器的新防御系统快要建好了，但是当正在数据库升级的时候，突然有黑客入侵机房网络，但是就在那时，插网线的房间钥匙丢了。所以Admin开始做防御机房的工作。
　　不过，由于访问某台电脑可经过其他电脑加速，但是不能访问途经电脑，而且单位时间内一台电脑只能发出一条指令，指令不含嵌套指令，Admin只能一台一台的建立防御，幸好如此，黑客也是一台一台入侵，不过二人都会选择最优方案进行操作。所以Admin在主控端(教师端)不停的巡察各台电脑的同时，要求你在简短的时间内帮Admin计算一下哪些电脑将必然被入侵成功，以便于Admin及时做出额外的保护措施，如果所有可能被入侵的电脑都能被保护，那么请计算出将所有连接在主控端上的电脑做好防御所需的总时间。
　　注意：只有黑客的入侵时间短于Admin的防御时间，黑客才能成功入侵。

输入格式 InputFormat

第一行为两个正整数N，M，表示有N台电脑，M条网线。(黑客近似地看为第N台电脑，在机房外)
第二行为N-2个正整数，表示每台电脑的访问时间t。
第三行到第 M+2 行，每行三个整数u,v,w，表示电脑u和v之间有一条网线，使用该网线互相到达对方电脑需要w个单位时间。

输出格式 OutputFormat

输出共两行。
如果有可能会防御失败的电脑，第一行输出"No"，第二行升序输出这些电脑的编号(空格隔开)。
否则第一行输出"Yes"，第二行输出将所有连接在主服务器上的电脑做好防御所需的总时间。

样例输入 SampleInput [复制数据]

[Sample 1]
4 6
1 2
1 2 10
1 3 5
1 4 1
2 3 4
2 4 1
3 4 10

[Sample 2]
5 7
1 1 1
1 2 70
1 3 70
1 4 70
1 5 70
2 5 70
3 5 70
4 5 70

样例输出 SampleOutput [复制数据]

[Sample 1]
No
2

[Sample 2]
Yes
213

数据范围和注释 Hint

样例解释：
第一组：由于1->2:2，4->2:1，所以2号电脑会被入侵成功
第二组：1到2,3,4点的时间均为71,5到2,3,4点的时间均为71，防御成功

对于20% 的数据，1 <=  N  <= 1000 ，1 <=  M  <= 2000
对于60% 的数据，1 <=  N  <= 5000 ，1 <=  M  <= 100000
对于100%的数据，1 <=  N  <= 10000，1 <=  M  <= 200000
对于100%的数据，1 <= t,w <= 10000，1 <= u,v <= N
提示：由于学生贪玩，有可能某个电脑没有连接主机，却接入网络；当然也有部分同学上课被禁网了。

时间限制 TimeLimitation

1s

来源 Source

tjz

这题就是Spfa.


Program defence;
const
   maxn=90000;
   maxm=500000;
   inf=2139062143;
type
   dis_arr=record
              s:longint;
              d:array[1..maxn] of longint;
           end;
var
   n,m,i,j:longint;
   w:array[1..maxn] of longint;
   head,edge,next,weight:array[1..maxm] of longint;
   size:longint;
   d1,d2:dis_arr;
   queue:array[1..6000000] of longint;

Procedure addedge(u,v,w:longint);
begin
   inc(size);
   edge[size]:=v;
   weight[size]:=w;
   next[size]:=head[u];
   head[u]:=size;
end;
Procedure addedge_main;
var
   u,v,w:longint;
begin
   read(u,v,w);
   addedge(u,v,w);addedge(v,u,w);
end;
Procedure spfa(var d:dis_arr);
var
   i,j,now,p:longint;
begin
   i:=1;j:=1;queue[1]:=d.s;
   fillchar(d.d,sizeof(d.d),127);d.d[d.s]:=0;
   while (i<=j) do
   begin
      now:=queue[i];
      p:=head[now];
      while (p<>0) do
      begin
         if (d.d[now]+weight[p]<d.d[edge[p]]) then
         begin
            inc(j);
            queue[j]:=edge[p];
            d.d[edge[p]]:=d.d[now]+weight[p];
         end;
         p:=next[p];
      end;
      inc(i);
   end;
end;
Procedure print;
var
   i,j:longint;
   ans:int64;
   flag:boolean;
begin
   flag:=false;    ans:=0;
   for i:=2 to n-1 do
   begin
      if d1.d[i]<>inf then ans:=ans+int64(w[i]+d1.d[i]);
      if (d1.d[i]>d2.d[i]) then
      begin
         if not(flag) then begin flag:=true; writeln('No'); end
         else write(' ');
         write(i);
      end;
   end;
   if not(flag) then
   begin
      writeln('Yes');
      writeln(ans);
   end
   else writeln;
end;
begin
//   assign(input,'defence.in');
//   reset(input);
   fillchar(head,sizeof(head),0);
   fillchar(edge,sizeof(edge),0);
   fillchar(next,sizeof(next),0);
   size:=0;
   read(n,m); d1.s:=1;d2.s:=n;
   for i:=2 to n-1 do read(w[i]);
   for i:=1 to m do
   begin
      addedge_main;
   end;
   spfa(d1);spfa(d2);
   print;
end.

HDU 3265(矩形面积并-分割矩形)

Posted on by

Posters

Problem Description
有很多海报，每个海报都被减去了一个矩形（可能全减），现在给出没张海报的位置，求它们的面积并。
保证坐标在(0, 0)到(50000, 50000)之间。没有海报斜着贴，减去的矩形边与x,y轴平行。
 
Input
有很多数据。
对于每组数据第一行有一个整数N (0<N<=50000)表示海报数 接下来n行，每行8个整数 x1, y1, x2, y2, x3, y3, x4, y4, 表示每张海报的左下角坐标(x1, y1),右上角坐标(x2, y2) ,减去的矩形左上角坐标(x3, y3),右上角坐标(x4, y4)(0<=xi, yi<=50000(i=1…4) and x1<=x3<x4<=x2, y1<=y3<y4<=y2).

数据以0结尾。
 


Output
对于每组数据输出一行，表示它们的面积并。
 


Sample Input
2
0 0 10 10 1 1 9 9
2 2 8 8 3 3 7 7
0
 


Sample Output
56
 

这题就是要把矩形差分成如下形式：



然后进行矩形面积并：

谨记问题转化后各数组的大小。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (50000+10)
#define MAXT (MAXN*5)
#define MAXXi (50000+10)
#define Lson (x<<1)
#define Rson ((x<<1)^1)
int hpos[MAXN];
int x[MAXN*4]={0};
struct SegMent
{
    int x1,x2,h,type;
    SegMent(){}
    SegMent(int _x1,int _x2,int _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){}
    friend bool operator<(const SegMent a,const SegMent b){return a.h<b.h;}
};
int n,size;
struct SegMent_array
{
    SegMent a[MAXN*8];
    int size;
    SegMent_array():size(0)
    {
        memset(a,0,sizeof(a));
    }

    bool add(int x1,int x2,int y1,int y2)
    {
        if (x1==x2||y1==y2) return 0;
        else
        {
            a[++size]=SegMent(x1,x2,y1,1);
            a[++size]=SegMent(x1,x2,y2,-1);
            return 1;
        }
    }
}a;
struct SegMentTree
{
    long long sum[MAXT],cnt[MAXT],len[MAXT];
    int M,n;
    void fillchar(int _n)
    {
        n=_n;
        M=1;while (M-2<n) M<<=1;
        memset(sum,0,sizeof(sum));
        memset(cnt,0,sizeof(cnt));
        memset(len,0,sizeof(len));
        for (int i=M+1;i<=M+n;i++) len[i]=x[i-M+1]-x[i-M];
        for (int i=M-1;i>=1;i--) len[i]=len[i<<1]+len[(i<<1)^1];
    }
    void pushup(int x)
    {
		sum[x]=(cnt[x])?(len[x]):((x<M)?(sum[Lson]+sum[Rson]):0);
	}
	void update(int x)
	{
		while (x)
		{
			pushup(x);x>>=1;
		}
	}
    void insert(int l,int r,long long c)
	{
		if (l>r) return ;
		l=l-1+M;r=r+1+M;
		int ll=l,rr=r;
		for (;l^r^1;l>>=1,r>>=1)
		{
			if (~l&1) {cnt[l+1]+=c; pushup(l+1);}
			if (r&1) {cnt[r-1]+=c; pushup(r-1);}
		}
//		cout<<endl<<"Push:"<<ll<<' '<<rr<<endl;
		update(ll);update(rr);
	}
	void print()
	{
		for (int i=1;i<=2*M;i++) if (sum[i]) cout<<i<<':'<<sum[i]<<' ';
		cout<<endl;
		for (int i=1;i<=2*M;i++) if (cnt[i]) cout<<i<<':'<<cnt[i]<<' ';
		cout<<endl;
		cout<<endl;
	}
}t;


int main()
{
//  freopen("Hdu3265.in","r",stdin);
    while (scanf("%d",&n)!=EOF)
    {
		if (n==0) break;
	    for (int i=1;i<=n;i++)
    	{
        	int x1,y1,x2,y2,x3,y3,x4,y4;
	        scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
    	    a.add(x1,x3,y1,y4);
        	a.add(x3,x2,y1,y3);
	        a.add(x1,x4,y4,y2);
    	    a.add(x4,x2,y3,y2);
			x[i*4-3]=x1;x[i*4-2]=x2;x[i*4-1]=x3;x[i*4]=x4;
	    }
    	sort(x+1,x+4*n+1);
    	size=unique(x+1,x+4*n+1)-(x+1);
/* 		for (int i=1;i<=size;i++) cout<<x[i]<<' ';
    	cout<<endl;
*/
//		cout<<size;
    	for (int i=1;i<=size;i++) hpos[x[i]]=i;
		t.fillchar(size-1);

		sort(a.a+1,a.a+1+a.size);
//		cout<<'s';
//		for (int i=1;i<=a.size;i++) cout<<a.a[i].x1<<' '<<a.a[i].x2<<' '<<a.a[i].h<<' '<<a.a[i].type<<endl;
		long long ans=0;
		for (int i=1;i<=a.size;i++)
		{
			ans+=t.sum[1]*((long long)a.a[i].h-a.a[i-1].h);
			t.insert(hpos[a.a[i].x1],hpos[a.a[i].x2]-1,a.a[i].type);
/*			cout<<a.a[i].x1<<' '<<a.a[i].x2<<' '<<a.a[i].h<<' '<<a.a[i].type<<endl;
			cout<<ans<<endl;
			t.print();
*/		}
		cout<<ans<<endl;
		a.size=0;
	}
	return 0;
}




POJ 1151(矩形面积并）

Posted on by
Language:
Atlantis
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 13134   Accepted: 5050

Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the
total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input consists of several test cases. Each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <=
100000;0 <= y1 < y2 <= 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area. 
The input file is terminated by a line containing a single 0. Don't process it.

Output

For each test case, your program should output one section. The first line of each section must be "Test case #k", where k is the number of the test case (starting with 1). The second one must be "Total explored area: a", where a is the total explored area
(i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point. 
Output a blank line after each test case.

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00

Source

Mid-Central European Regional Contest 2000

同Hdu 1542，不过数据变水……


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<map>
using namespace std;
#define MAXN (2000+10)
#define MAXT (1000*2*10)
#define Lson (x<<1)
#define Rson ((x<<1)^1)
int tt,n,size;
double x[MAXN];
struct SegMent
{
    double x1,x2,h;
    int type;
    SegMent(){}
    SegMent(double _x1,double _x2,double _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){}
    friend bool operator<(const SegMent a,const SegMent b){return a.h<b.h;    }
}a[MAXN];
map<double , int>  hpos;
double len[MAXT];
struct SegMentTree
{
    int n,M,cnt[MAXT];
    double sum[MAXT];
    int mark[MAXT];
    void fillchar(int _n)
    {
        n=_n;
        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        memset(mark,0,sizeof(mark));
        M=1;while (M-2<n) M<<=1;
        x[0]=0;memset(len,0.0,sizeof(len));
        for (int i=M+1;i<=M+size;i++) len[i]=x[i-M]-x[i-M-1];
        for (int i=M-1;i>0;i--) len[i]=len[i<<1]+len[(i<<1)^1];
    }
    void pushup(int x)
    {
        sum[x]=cnt[x]?len[x]:(x>=M?0:sum[Lson]+sum[Rson]);
    }
    void update(int x)
    {
        for (;x;x>>=1)
        {
            pushup(x);
        }
    }

    void insert(int l,int r,int c)
    {
        int ll=l-1+M,rr=r+1+M;
        for (l=l-1+M,r=r+1+M;l^r^1;l>>=1,r>>=1)
        {
            if (~l&1) {cnt[l+1]+=c;pushup(l+1);} /*改变sum的值 */
            if (r&1) {cnt[r-1]+=c;pushup(r-1);}
        }
        update(ll);update(rr);
    }
}t;

int main()
{
//    freopen("Hdu1542.in","r",stdin);
    tt=0;
    while (scanf("%d",&n)!=EOF)
    {
        tt++;
        if (!n) break;
        for (int i=1;i<=2*n;i+=2)
        {
			double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            x[i]=x1;x[i+1]=x2;
            a[i]=SegMent(x1,x2,y1,1);
            a[i+1]=SegMent(x1,x2,y2,-1);
        }

        sort(a+1,a+2*n+1);
        sort(x+1,x+2*n+1);
        size=unique(x+1,x+2*n+1)-(x+1);
        for (int i=1;i<=size;i++) hpos[x[i]]=i;
        t.fillchar(size);


        double ans=0;a[0].h=a[1].h;
        for (int i=1;i<=2*n;i++)
        {
            ans+=(a[i].h-a[i-1].h)*t.sum[1];
            t.insert(hpos[a[i].x1]+1,hpos[a[i].x2],a[i].type);
        }
        printf("Test case #%dnTotal explored area: %.2lfnn",tt,ans);


    }
    return 0;
}

HDU 1542(矩形面积并）

Posted on by

Atlantis

Problem Description
已知Atlantis的地图由许多矩形构成，求它们的面积并。
 


Input
题目有多组数据，每组数据的开头有一个整数n(1<=n<=100)，表示地图数，接下来n行,每行4个小数 x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), 表示这张地图左上角坐标 (x1; y1)和右上角坐标 (x2;y2).
数据以0结束
 


Output
对于每组数据，你需要输出一行 “Test case #k”,k表示第k组数据(从1开始).第二行为“Total explored area: a”,a为面积并（保留2位小数），
每组数据后，请输出一个回车。
 


Sample Input
2
10 10 20 20
15 15 25 25.5
0
 


Sample Output
Test case #1
Total explored area: 180.00
 

矩形面积并入门题，

首先把直线拆成上边和下边，按高度排序，

横坐标离散化，建立线段树。

cnt[]表示某条线段被覆盖的次数，sum[]表示一条线段被覆盖的长度

我们在计算cnt[]时,没修改1个cnt[],就用pushup把sum[]更新，得到程序1：



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<map>
using namespace std;
#define MAXN (2000+10)
#define MAXT (1000*2*10)
#define Lson (x<<1)
#define Rson ((x<<1)^1)
int tt,n,size;
double x[MAXN];
struct SegMent
{
    double x1,x2,h;
    int type;
    SegMent(){}
    SegMent(double _x1,double _x2,double _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){}
    friend bool operator<(const SegMent a,const SegMent b){return a.h<b.h;    }
}a[MAXN];
map<double , int>  hpos;
double len[MAXT];
struct SegMentTree
{
    int n,M,cnt[MAXT];
    double sum[MAXT];
    int mark[MAXT];
    void fillchar(int _n)
    {
        n=_n;
        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        memset(mark,0,sizeof(mark));
        M=1;while (M-2<n) M<<=1;
        x[0]=0;memset(len,0.0,sizeof(len));
        for (int i=M+1;i<=M+size;i++) len[i]=x[i-M]-x[i-M-1];
        for (int i=M-1;i>0;i--) len[i]=len[i<<1]+len[(i<<1)^1];
    }
    void pushdown(int x)
    {
        if (x>>1) pushdown(x>>1);
        if (mark[x])
        {
            mark[Lson]+=mark[x];
            cnt[Lson]+=mark[x];
            mark[Rson]+=mark[x];
            cnt[Rson]+=mark[x];
            mark[x]=0;
        }
    }
    void pushup(int x)
    {
    //    pushdown(x);cout<<mark[5];
    //    cout<<x<<' ';

        sum[x]=cnt[x]?len[x]:(x>=M?0:sum[Lson]+sum[Rson]);
    }
    void update(int x)
    {
        for (;x;x>>=1)
        {
        //    cout<<"push "<<x<<endl;
            pushup(x);
        }
    }

    void insert(int l,int r,int c)
    {
        int ll=l-1+M,rr=r+1+M;
        for (l=l-1+M,r=r+1+M,pushdown(l>>1),pushdown(r>>1);l^r^1;l>>=1,r>>=1)
        {
            if (~l&1) {cnt[l+1]+=c;update(l+1);/*mark[l+1]+=c;*/} /*改变sum的值 */
            if (r&1) {cnt[r-1]+=c;update(r-1);/* mark[r-1]+=c;*/}
        }
//        update(ll);update(rr); //向上传递
    }
    void print()
    {
        cout<<"cnt ";
        for (int i=1;i<=M*2;i++) if (cnt[i]) cout<<i<<':'<<cnt[i]<<' ';
        cout<<endl;
        cout<<"sum ";
        for (int i=1;i<=M*2;i++) if (sum[i]) cout<<i<<':'<<sum[i]<<' ';
        cout<<endl;
        cout<<"Mark ";
        for (int i=1;i<=M*2;i++) if (mark[i]) cout<<i<<':'<<mark[i]<<' ';
        cout<<endl;
    }
}t;

int main()
{
//    freopen("Hdu1542.in","r",stdin);
    tt=0;
    while (scanf("%d",&n)!=EOF)
    {
        tt++;
        if (!n) break;
        for (int i=1;i<=2*n;i+=2)
        {
            scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].h,&a[i].x2,&a[i+1].h);
            a[i+1].x1=a[i].x1; a[i+1].x2=a[i].x2;
            a[i].type=1;a[i+1].type=-1;
            x[i]=a[i].x1;x[i+1]=a[i].x2;
        }
        sort(a+1,a+2*n+1);
//        for (int i=1;i<=2*n;i++) cout<<a[i].x1<<' '<<a[i].x2<<' '<<a[i].h<<' '<<a[i].type<<endl;

        sort(x+1,x+2*n+1);
        size=unique(x+1,x+2*n+1)-(x+1);
//        for (int i=1;i<=size;i++) cout<<x[i]<<' ';cout<<endl;

        for (int i=1;i<=size;i++) hpos[x[i]]=i;

        t.fillchar(size);
/*        for (int i=1;i<=t.M*2;i++) cout<<len[i]<<' ';
        cout<<endl;
*/        /*
        t.insert(1,3,1);t.print();
        t.insert(2,4,2);
        cout<<t.find(1,3);
        cout<<endl;
        t.print();
        */
    //    t.insert(2,3,1);
        /*
        t.insert(2,3,1);
        t.print();
        t.insert(3,4,1);
        t.print();
        t.insert(2,3,-1);
        t.print();

        */

        double ans=0;a[0].h=a[1].h;
        for (int i=1;i<=2*n;i++)
        {
            ans+=(a[i].h-a[i-1].h)*t.sum[1];
            t.insert(hpos[a[i].x1]+1,hpos[a[i].x2],a[i].type);
/*            t.print();
            cout<<hpos[a[i].x1]+1<<' '<<hpos[a[i].x2]<<endl;
            cout<<t.sum[1]<<endl;
            cout<<ans<<endl;
*/        }
        printf("Test case #%dnTotal explored area: %.2lfnn",tt,ans);


    }
    return 0;
}

上述程序效率较慢(m(logm)^2) ,m为边数


我们考虑到，每次上传实在太耗时了。

仔细观察方程，发现每次修改的点一定是从叶结点到根节点的路上的结点的兄弟（不包括路上）

因此每次被影响的一定是路上的结点。

故我们每次只更新结点的值，最后直接由根节点向上递归，得到程序2-效率为O(mlogm) ：


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<map>
using namespace std;
#define MAXN (2000+10)
#define MAXT (1000*2*10)
#define Lson (x<<1)
#define Rson ((x<<1)^1)
int tt,n,size;
double x[MAXN];
struct SegMent
{
    double x1,x2,h;
    int type;
    SegMent(){}
    SegMent(double _x1,double _x2,double _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){}
    friend bool operator<(const SegMent a,const SegMent b){return a.h<b.h;    }
}a[MAXN];
map<double , int>  hpos;
double len[MAXT];
struct SegMentTree
{
    int n,M,cnt[MAXT];
    double sum[MAXT];
    int mark[MAXT];
    void fillchar(int _n)
    {
        n=_n;
        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        memset(mark,0,sizeof(mark));
        M=1;while (M-2<n) M<<=1;
        x[0]=0;memset(len,0.0,sizeof(len));
        for (int i=M+1;i<=M+size;i++) len[i]=x[i-M]-x[i-M-1];
        for (int i=M-1;i>0;i--) len[i]=len[i<<1]+len[(i<<1)^1];
    }
    void pushup(int x)
    {
        sum[x]=cnt[x]?len[x]:(x>=M?0:sum[Lson]+sum[Rson]);
    }
    void update(int x)
    {
        for (;x;x>>=1)
        {
            pushup(x);
        }
    }

    void insert(int l,int r,int c)
    {
        int ll=l-1+M,rr=r+1+M;
        for (l=l-1+M,r=r+1+M;l^r^1;l>>=1,r>>=1)
        {
            if (~l&1) {cnt[l+1]+=c;pushup(l+1);} /*改变sum的值 */
            if (r&1) {cnt[r-1]+=c;pushup(r-1);}
        }
        update(ll);update(rr);
    }
}t;

int main()
{
//    freopen("Hdu1542.in","r",stdin);
    tt=0;
    while (scanf("%d",&n)!=EOF)
    {
        tt++;
        if (!n) break;
        for (int i=1;i<=2*n;i+=2)
        {
			double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            x[i]=x1;x[i+1]=x2;
            a[i]=SegMent(x1,x2,y1,1);
            a[i+1]=SegMent(x1,x2,y2,-1);
        }

        sort(a+1,a+2*n+1);
        sort(x+1,x+2*n+1);
        size=unique(x+1,x+2*n+1)-(x+1);
        for (int i=1;i<=size;i++) hpos[x[i]]=i;
        t.fillchar(size);


        double ans=0;a[0].h=a[1].h;
        for (int i=1;i<=2*n;i++)
        {
            ans+=(a[i].h-a[i-1].h)*t.sum[1];
            t.insert(hpos[a[i].x1]+1,hpos[a[i].x2],a[i].type);
        }
        printf("Test case #%dnTotal explored area: %.2lfnn",tt,ans);


    }
    return 0;
}





POJ 3487(稳定婚姻问题)

Posted on by
Language:
The Stable Marriage Problem
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 1941   Accepted: 827

Description

稳定婚姻系统问题如下

  • 集合M 表示n个男性;
  • 集合 F 表示n个女性;
  • 对于每个人我们都按异性的中意程度给出一份名单(从最中意的到最不中意的).

如果没有(m, f) , f ∈ F,m ∈ M f对m比对她的配偶中意的同时m对f比对他的配偶更加中意，那这个婚姻是‘稳定’的.如果一个稳定配对不存在另一个稳定婚姻配对，其中所有的男性的配偶都比现在强，那么这个稳定配对称为男性最优配对。

Input

第一行为数据数.

对于每组数据，第一行为n (0 < n < 27).接下来一行依次为男性的名字（小写字母）和女性的名字（大写字母）接下来 n 行为每个男性的中意程度名单（从大到小)，接下来n行是女性的中意程度名单（同上）.

Output

输出一组男性最优配对，男性按字典序从小到大排列，每行为“男性名 女姓名”的形式；

每数据后输出一空行。

Sample Input

2
3
a b c A B C
a:BAC
b:BAC
c:ACB
A:acb
B:bac
C:cab
3
a b c A B C
a:ABC
b:ABC
c:BCA
A:bac
B:acb
C:abc

Sample Output

a A
b B
c C

a B
b A
c C

Source

Southeastern Europe 2007

这题是很经典的稳定婚姻系统问题,它的解法为“求婚-拒绝”算法：

======================================================================================================

稳定婚姻问题的经典算法为求婚-拒绝算法(propose-and-reject algorithm)，即
男士按自己喜欢程度从高到低依次给每位女士主动求婚，直到有一个接受他。女士每
次遇到比当前配偶更差的男士时拒绝他，遇到更喜欢的男士时就接受他，并抛弃以前
的配偶。被抛弃的男士继续按照列表向剩下的女士依次求婚，直到所有人都有配偶。
看起来女士更有选择权，但实际上最后得到的结果是男士最优(man-optimal)的。下
面我们详细描述这一算法并证明相应的结论。
如果算法最后得到了一个匹配，那么它一定是稳定的。为了证明这一点，我们首
先注意到随着算法的执行，每位女士的配偶越来越好，而每位男士的配偶越来越差。
因此假设男士u和女士v形成不稳定对，u一定曾经向v求过婚，但被拒绝。这说明v当时
的配偶比u更好，因此算法结束后的配偶一定仍比u好，和不稳定对的定义矛盾。
下面我们只需要说明算法一定成功结束，即不会存在一位男士u，使得他向所有
女士求婚后仍为单身。假设存在这样的人，设其中最后一次被抛弃时刻最晚的男士
为u，则他最后一次被抛弃时无配偶，因此当时一定存在女士v也没有配偶。由于v是单
身的，所以一定没有人向她求过婚，因此v还在u的考虑范围之中，以后会向v求婚。到
432 图论问题和算法
时u会再次有配偶，要么还将被抛弃一次，要么最后不会单身，无论哪种情况都将产生
矛盾。
这样，我们证明了算法一定得到稳定匹配。时间复杂度显然是O(n2)，因此每个男
士最多考虑每个女士各一次，每次的时间复杂度均为O(1)。显然这已经是时间复杂度
的下限了，因为输入是O(n2)的。
如果存在一个稳定匹配使得男士i和女士j配对，则称(i,j)是稳定对。对于每个男
士i，设所有稳定对(i,j)中i 最喜欢的女士为best(i)，则可以证明这里给出的算法对让每
位男士i与best(i)配对。对于所有男士来说，不会有比这更好的结果了，而对于女士则
恰恰相反——对于她们来说不会有比这更糟的结果了。

=================================================================================================================


Program p3487;
const
   maxn=26;
var
   tt,n,i,j,k:longint;
   nam:array[1..2,1..maxn] of char;
   female_like:array['A'..'Z','a'..'z'] of longint;
   male_like:array['a'..'z',1..maxn] of char;

   a:array['a'..'z'] of char;
   b:array['A'..'Z'] of char;

   s:string;
   c:char;
   q:array[1..maxn*maxn] of char;
   h,t:longint;
   now,v:char;
begin
   readln(tt);
   while (tt>0) do
   begin
      fillchar(a,sizeof(a),' ');
      fillchar(b,sizeof(b),' ');
      readln(n);
      for k:=1 to 2 do
         for i:=1 to n do
         begin
            read(nam[k,i]);
            read(c);
         end;
      readln;
      for i:=1 to n do
      begin
         readln(s);
         for j:=3 to length(s) do male_like[s[1],j-2]:=s[j];
      end;
      for i:=1 to n do
      begin
         readln(s);
         for j:=3 to length(s) do female_like[s[1],s[j]]:=n+1-(j-2);
      end;

      h:=1;t:=n;
      for i:=1 to n do q[i]:=nam[1,i];
      while h<=t do
      begin
         now:=q[h];
         for i:=1 to n do
         begin
            v:=male_like[now,i];
            if (b[v]=' ') then
            begin
               a[now]:=v;
               b[v]:=now;
               break;
            end;
            if (female_like[v,b[v]]<female_like[v,now]) then
            begin
               inc(t);
               q[t]:=b[v];
               a[b[v]]:=' ';
               a[now]:=v;
               b[v]:=now;
               break;
            end;
         end;
         inc(h);
      end;


      for now:='a' to 'z' do if a[now]<>' ' then writeln(now,' ',a[now]);
      writeln;


      dec(tt);
   end;

end.

POJ 3171(区间覆盖最小代价）

Posted on by
Language:
Cleaning Shifts
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 2093   Accepted: 735

Description

有N (1 <= N <= 10,000)个区间，求覆盖[M,E](0 <= M <= E <= 86,399)的最小代价.
每个区间的代价为S (where 0 <= S <= 500,000).

Input

第一行3个整数: N, M, E. 

第二行到第n+1行，每行3个数，分别表示第i-1个区间的左端点T1,右端点T2,和代价S.

Output

仅一行表示最小代价，无解输-1.

Sample Input

3 0 4
0 2 3
3 4 2
0 0 1

Sample Output

5

Hint

样例解释
取第一个和第二个区间。

Source

USACO 2005 December Silver

这题是一个Dp问题，先列出Dp方程。
F[i]表示取[M,i]这个区间的代价
显然F[M-1]=0,答案就是F[E]
则方程为F[a[i].T2]=min(F[j])+a[i].S (T1-1<=J<=T2-1)
a[i]按T2从小到大排列；
那么显然a[i]取时，[M,T1-1]已经被前面的给取了，
因为如果被后面的[t1,t2] 取了,那么必有t1<T1 T2<t2， 就没必要取[T1,T2]了。

取最小的数可以用线段树做O(NlogN)。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (10000+10)
#define MAXE (86399)
#define MAXS (500000+10)
#define INF (9187201950435737471)
int n,s,e;
struct SegMent
{
	int l,r;
	long long S;
	SegMent(){}
	SegMent(int _l,int _r,long long _S):l(_l),r(_r),S(_S){}
	friend bool operator<(const SegMent a,const SegMent b){return a.r<b.r;}
}a[MAXN];
struct SegMentTree //min()
{
	int n,M;
	long long t[MAXE*10];
	void fillchar(int _n)
	{
		n=_n+2;
		M=1;while (M-2<n) M<<=1;
		memset(t,127,sizeof(t));
	}
	void update(int x)
	{
		for (x>>=1;x;x>>=1) t[x]=min(t[x<<1],t[(x<<1)^1]);
	}
	void insert(int x,long long c)
	{
		x=x+2;
		x+=M;
		if (t[x]>c) {t[x]=c; update(x);	}
	}
	long long find(int l,int r)
	{
		l=l+2;r=r+2;

		l=l-1+M;r=r+1+M;
		long long ans=INF;
		while (l^r^1)
		{
			if (~l&1) ans=min(ans,t[l+1]);
			if (r&1) ans=min(ans,t[r-1]);
			l>>=1;r>>=1;
		}
		return ans;
	}
}t;
int main()
{
//	freopen("poj3171.in","r",stdin);
	scanf("%d%d%d",&n,&s,&e);
	for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].S);
	sort(a+1,a+1+n);
	t.fillchar(e);
	t.insert(s-1,0);
	for (int i=1;i<=n;i++)
	{
		if (a[i].r<s) continue;
		t.insert(a[i].r,t.find(max(s-1,a[i].l-1),a[i].r-1)+a[i].S);
	}
/*	for (int i=t.M;i<=t.M*2;i++) cout<<t.t[i]<<' ';
	cout<<endl;
*/	if (t.t[e+2+t.M]==INF) cout<<"-1n";
	else cout<<t.t[e+2+t.M]<<endl;


	return 0;
}

BZOJ 2547(匈牙利算法-任意边的处理)

Posted on by

2547: [Ctsc2002]玩具兵

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 104  Solved: 50
[Submit][Status][Discuss]

Description

小明的爸爸给他买了一盒玩具兵，其中有 K个步兵，K个骑兵和一个天兵，个个高大威猛，形象逼真。盒子里还有一个M*N棋盘，每个格子(i,j)都有一个高度Hij，并且大得足以容纳所有的玩具兵。小明把所有的玩具兵都放到棋盘上去，突然想到了一种很有趣的玩法：任意挑选T个不同的格子，并给每个格子i规定一个重要值Ri­­，游戏的目标就是每次沿东南西北之一的方向把一个玩具兵移动到其相邻的格子中（但不能移动到棋盘外面去），最终使得每个挑选出的格子i上恰好有Ri个玩具兵。小明希望所有的玩具兵都在某个选定的格子中，因此他总是使选出的T个格子的重要值之和等于玩具兵的个数。为了增加难度，小明给玩具兵们的移动方式做了一些规定：

●  步兵只会往高处爬，因此如果两个格子A和B相邻，当且仅当格子A的高度小于或等于B，步兵才可以从A移动到B。

●      骑兵只会往低处跳，因此如果两个格子A和B相邻，当且仅当格子A的高度大于或等于B，骑兵才可以从A移动到B。

●      天兵技术全面，移动不受任何限制。

       可是没玩几次，小明就发现这个游戏太难了，他常常玩了好半天也达不到目的。于是，他设计了一种“超能力”，每使用一次超能力的时候，虽然不能移动任何一个玩具兵，但可对它们进行任意多次交换操作，每次交换两个玩具兵。等这次超能力使用完后又可和平常一样继续移动这些玩具兵。借助强大的超能力，这个游戏是容易玩通的，但是怎样才能让使用超能力的次数最少呢？

 

Input

第一行包含四个整数：M,N,K,T (2<=M,N<=100, 1<=K<=50, 1<=T<=2K+1)

    第二行包括2K+1个数对(xi,yi)，代表各个玩具兵的初始位置。前K个代表步兵，接下来的K个代表骑兵，最后一个代表天兵。

    第三行包含T个三元组(xi,yi,ri)，第i组代表第i个目标格的位置和重要值。

        以下M行，每行N个整数。其中第i行第j个数为即格子的高度Hij。高度是不超过100的正整数，注意：不同玩具兵的初始位置可能相同。输入数据保证无错，选定的T个格子的重要值之和保证等于2K+1。

Output

仅包含一行，即使用超能力的最小次数T。

Sample Input

4 6 2 5

1 1 1 5 4 1 4 5 3 3

1 2 1 2 6 1 3 2 1 3 6 1 4 3 1

3 2 6 1 3 5

2 1 7 4 4 6

2 3 1 4 3 4

4 3 4 3 2 3

Sample Output

1

先来分析一下这个问题。
1.显然天兵的初始位置不重要。
2.最坏情况不断使用天兵，2*k次便能解决.

不妨假设不存在天兵：
1.我们把调换位置-改为调换兵种（显然成立），那么一个棋子一定调换（否则移到需要的位置调换）.
2.显然如果我有确定的‘超能力’次数，那么任何一个棋子所能到达的地方有限（bfs）。
3.显然我们可以判断1个棋子在超能力步数内必须到达另一个棋子（就是这个棋子，无论怎么调换兵种）.
问是否是合法方案   
那么这就是一个二分图匹配，必须完全匹配。

天兵的意义
1.显然一个天兵可以在棋盘上随便走，在每次调换时，找一个棋子把它挪到目的地
   这相当于在二分图上任意填‘超能力次数’条边。
故先算出最大匹配数，再+超能力数，可以得到最优方案

模型建毕：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN (100+10)
#define MAXM (100+10)
#define MAXK (100+10)
#define MAXT (100+1+10)
#define COST (bool(type)^(f[x][y]&1))?(h[x][y]<h[x+path[i][0]][y+path[i][1]]):(h[x][y]>h[x+path[i][0]][y+path[i][1]])
const int path[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,m,k,t,h[MAXM][MAXN],f[MAXM][MAXN];
queue< pair<int,int> > q;
bool inside(int x,int y)
{
	if (1<=x&&x<=m&&1<=y&&y<=n) {/*cout<<'A'<<x<<' '<<y<<endl;*/ return 1;}else return 0;
}
void bfs(bool type,int x,int y)  //type-> 0 upper 1 lower
{
	memset(f,127,sizeof(f));
	f[x][y]=0;
	q.push(make_pair(x,y));
	while (!q.empty())
	{
		pair<int ,int> now=q.front();
		int &x=now.first,&y=now.second;
		for (int i=0;i<4;i++)
		{
			int c=COST;
			if (inside(x+path[i][0],y+path[i][1]))
				if (f[x+path[i][0]][y+path[i][1]]>f[x][y]+c)
			{
		//		cout<<(x+path[i][0])<<' '<<(y+path[i][1])<<endl;
				f[x+path[i][0]][y+path[i][1]]=f[x][y]+c;
				q.push(make_pair(x+path[i][0],y+path[i][1]));
			}
		}
		q.pop();
	}
}
pair<int,int> A[MAXT],B[MAXT];
int cost[MAXK][MAXT],a[MAXT];
bool b[MAXT];
bool find(int x,int maxcost)
{
	for (int i=1;i<=2*k+1;i++)
		if (!b[i]&&cost[x][i]<=maxcost)
		{
			b[i]=1;
			if (a[i]==0) {a[i]=x;return 1;	}
			if (find(a[i],maxcost)) {a[i]=x; return 1;	}
		}
	return 0;
}
int hopcroft(int maxcost)
{
	memset(a,0,sizeof(a));
	int ans=0;
	for (int i=1;i<=2*k;i++)
	{
		memset(b,0,sizeof(b));
		if (find(i,maxcost)) ans++;
	}
//	cout<<ans<<endl;
	return ans;
}
int b_search()
{
	int l=0,r=2*k;
	while (l<r)
	{
		m=(l+r)>>1;
		if (hopcroft(m)+m>=2*k) r=m;
		else l=m+1;
	}
	return l;
}
int main()
{
//	freopen("2547.in","r",stdin);
	scanf("%d%d%d%d",&m,&n,&k,&t);
	for (int i=1;i<=2*k+1;i++) scanf("%d%d",&A[i].first,&A[i].second);
	int size=1;
	for (int i=1;i<=t;i++)
	{
		int r;
		scanf("%d%d%d",&B[size].first,&B[size].second,&r);
		size++;
		for (r--;r;r--,size++) B[size]=B[size-1];
	}
	for (int i=1;i<=m;i++)
		for (int j=1;j<=n;j++)
			scanf("%d",&h[i][j]);

/*	bfs(1,1,2);
	for (int i=1;i<=m;i++)
	{
		for (int j=1;j<=n;j++) cout<<f[i][j]<<' ';
		cout<<'n';
	}
*/
	for (int i=1;i<=2*k;i++)
	{
		bfs((i>k),A[i].first,A[i].second);
		for (int j=1;j<=2*k+1;j++)
		{
			cost[i][j]=f[B[j].first][B[j].second];
//			cout<<i<<' '<<j<<' '<<cost[i][j]<<endl;
		}
	}

	cout<<b_search()<<endl;


	return 0;
}

C++ pair

Posted on by

Pair类型概述

pair是一种模板类型，其中包含两个数据值，两个数据的类型可以不同，基本的定义如下：

 

pair<int, string> a;

表示a中有两个类型，第一个元素是int型的，第二个元素是string类型的，如果创建pair的时候没有对其进行初始化，则调用默认构造函数对其初始化。

 

pair<string, string> a("James", "Joy");

也可以像上面一样在定义的时候直接对其初始化。

 

由于pair类型的使用比较繁琐，因为如果要定义多个形同的pair类型的时候，可以时候typedef简化声明：

typedef pair<string, string> author;

author pro("May", "Lily");

author joye("James", "Joyce");

 

 

Pair对象的操作

 

  • 对于pair类，由于它只有两个元素，分别名为first和second，因此直接使用普通的点操作符即可访问其成员

pair<string,
string> a("Lily", "Poly"); 

string
name;

name
= pair.second;

  • 生成新的pair对象

可以使用make_pair对已存在的两个数据构造一个新的pair类型：

int a = 8;

string m = "James";

pair<int, string> newone;

newone = make_pair(a, m);

 

 

POJ 2355(区间最大值-zkw线段树优化Dp方程）

Posted on by
Language:
Railway tickets
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 2379   Accepted: 823

Description

从1号车站Ekaterinburg到n号车站Sverdlovsk有一条铁路。 


订票时票价如下

2车站间的距离 -X

价格t

0<X<=L1

C1

L1<X<=L2

C2

L2<X<=L3

C3



由于总总原因，距离超过L3的车票不能定。
现在你打算从s号车站乘铁路到t号车站，求最小费用。

Input

第一行有6个数 L1, L2, L3, C1, C2, C3 (1 <= L1 < L2 < L3 <= 10^9, 1 <= C1 < C2 < C3 <= 10^9)
第二行为车站数N (2 <= N <= 10000)
第三行为s和t，表示起点和终点.
接下来n-1行，表示从第1好车站到第i(1<i<=n)号车站的距离（保证是升序）.

Output

仅一行，为最小费用(<10^9)

Sample Input

3 6 8 20 30 40
7
2 6
3
7
8
13
15
23

Sample Output

70

Source

Ural Collegiate Programming Contest 1999

这题就是Dp

显然F[i]=F[j]+c[k](j<i,a[j]-a[i]<=l[k],1<=k<=3) F[i]表示从起点s到车站i的最小费用。 

用显然j单调递增，可用指针向后推（O(n)）

注意判断INF为无解情况，可能超过变成负数，线段树记得开大


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20000+10)
#define INF (2139062143)
int l[4],c[4],n,a[MAXN],st,en;
struct SegMentTree
{
	int t[MAXN*10],n,M;
	SegMentTree(){}
	SegMentTree(int _n):n(_n)
	{
		M=1;while (M-2<n) M<<=1;
		memset(t,127,sizeof(t));
	}
	void update(int x)
	{
		for (x>>=1;x;x>>=1) t[x]=min(t[x<<1],t[(x<<1)^1]);
	}
	void insert(int x,int c)
	{
		x+=M;
		if (t[x]>c)
		{
			t[x]=c;//cout<<endl<<'I'<<x<<' '<<c<<endl;
			update(x);
		}
	}
	int find(int l,int r)
	{
		if (l>r) return INF;
		l=l-1+M;r=r+1+M;
		int ans=INF;
		while (l^r^1)
		{
			if (~l&1) ans=min(ans,t[l+1]);
			if (r&1) ans=min(ans,t[r-1]);
			l>>=1;r>>=1;
		}
		return ans;
	}
}t;
void push(int &j,int L,int i)
{
	while (a[i]-a[j]>L) j++;
}
int main()
{
	scanf("%d%d%d%d%d%d%d",&l[1],&l[2],&l[3],&c[1],&c[2],&c[3],&n);
	t=SegMentTree(n);
	scanf("%d%d",&st,&en);if (st>en) swap(st,en);
	if (st==en) {cout<<"0"<<endl;return 0;	}
	a[1]=0;
	for (int i=2;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int j[4]={st,st,st,st};
	t.insert(st,0);
	for (int i=st+1;i<=en;i++)
	{
		int value=INF;
		for (int k=1;k<=3;k++)
		{
			push(j[k],l[k],i);
//			cout<<j[k]<<' ';
			int p=t.find(j[k],i-1);
			if (p<INF) p+=c[k];
			value=min(value,p);
		}
//		cout<<value<<' '<<endl;
		t.insert(i,value);
//		for (int i=1;i<=t.M*2;i++) if (t.t[i]-INF) cout<<i<<' '<<t.t[i]<<' ';
//		cout<<endl;
	}
	cout<<t.find(en,en)<<endl;
	return 0;
}