注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

GCJ 2009 Final E Marbles  

2014-09-23 10:31:53|  分类: 集训队作业 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://tsinsen.com/P5513
这个题目比较有意思。
给2n个数的序列,保证1到n每个数都出现了2次。现在要用线给连起来,要求只能用横线和竖线,并且线之间不能触碰相交,也不能穿过x轴。问是否有解,如果有解,还要计算最上与最下的线的高度差的最小值。
例如序列1 1 2 3 2 3,可以这么连:

+-+ +---+

| | | |

1 1 2 3 2 3

| |

+---+

这样的高度是2,而且是最优的。
n≤500,数据组数≤50。
Solution
一开始不小心想成了双栈排序,但是这题不仅对出栈顺序有要求,还对出栈时间有要求。不过,这个想法给我提供了一个关于二分图的思路。
这2n的序列可以转化成n个区间。对于每个区间,我们需要决定它是放在上面还是下面。
两个区间的关系可能是:没有交集,互相包含,和普通的相交三个情况。显然,如果两个区间相交(指不包含的相交),那么它们不能在x轴的同侧。
于是把每个区间看成图的顶点,按照这个排斥关系连边,看这个图是不是二分图就行了。不是二分图就无解。
是二分图就是有解的,这个可以比较直观地看出来。
如果考虑暴搜,那么可以这样做:对于二分图中的每个连通块,我们要决定其中的某个元素在上面还是下面(然后连通块中的其他元素就确定了)。2^连通块数枚举以后问题就变成了找一个括号序列的最大嵌套层数,这个小学生都会做。
==========以上内容都是废话==========
考虑一些其他的性质。
结论:对于两个连通块A和B,如果A中的任何一个区间a被B中的某个区间B包含,那么A中的所有区间都会被b包含。
直观理解是正确的,因为对于A中的任何一个区间x,它一定与a间接相交(x与p相交,p与q相交……最后与a相交),如果x不被b包含,那么这一系列的区间(x,p,q...)一定会有一个与b相交,那么A和B就连通了。
所以不难得出,对于两个连通块A和B,要么A和B完全没有公共部分,要么有一个被另一个完全包含(即某一个的所有区间都被另一个的某个区间包含)。
为了方便,我们加入一个区间[0,2n+1],这个区间包含了所有的区间,且单独成一个连通块。这样,所有连通块就按照包含关系,形成了一个以这个连通块为根的有根树。
然后做树dp。设dp[A][i]表示:只考虑连通块A的子树中的区间,要求向上的高度不超过i,这时的向下的高度的最小值。
为了算这个,我们需要以下几个东西:
A的二分图的每个独立顶点集所对应的区间的最大覆盖高度;(这个好像还要做个小dp……)
对于A的每个孩子,要计算对于这个孩子的任何一个区间,A中的包含这个区间的区间个数(=_=||);
A的每个孩子的dp值。
然后转移的时候就枚举孩子是正着覆盖上去还是反着覆盖上去。
转移完后还要进行松弛:dp[A][i+1]=min(dp[A][i],dp[A][i+1])
还要把上下反过来再算一遍取个min。
最后枚举i,找一个dp[root][i]+i的最小值就是答案了。

代码跟上面的思路有点小出入,但是大概意思是一样的……
#define a first
#define b second
map<string, int> S;

inline string gg(){
	char s[12]; scanf("%s", s); return string(s);
}

int n, cn = 0;
PII inv[508];

inline bool cross(PII x, PII y){
	return
	(x.a < y.a && y.a < x.b && x.b < y.b)
	||
	(y.a < x.a && x.a < y.b && y.b < x.b)
	;
}
inline bool contain(PII x, PII y){
	return x.a < y.a && y.b < x.b;
}
inline bool bylen(PII x, PII y){
	return x.b - x.a < y.b - y.a;
}

int col[508];

struct Tuo;
vector<Tuo *> tuos;
typedef std::pair<Tuo *, PII> PTP;

#define INF 10086
//a Tuo of intervals 233
struct Tuo{
	int dp[2][508];
	vector<PII> ins[2];
	PII first;
	vector<PTP> children;
	int maxx, minx, len;
	bool root;
	inline Tuo(){
		root = true; maxx = 0; minx = INF;
	}
	inline void dfs(int x, int c){
		if(col[x] != -1){
			if(col[x] != c) throw 233;
			return;
		}else{
			col[x] = c; first = inv[x];
			ins[c].push_back(first);
			if(first.a < minx) minx = first.a;
			if(first.b > maxx) maxx = first.b;
			len = maxx - minx;
			f(i, 1, n) if(i != x && cross(inv[i], inv[x])) dfs(i, 1 - c);
		}
	}
	inline void findChildren(){
		foreach(it, tuos){
			Tuo *tuo = *it;
			if(tuo == this) break;
			if(!tuo->root) continue;
			int height[2]; height[0] = height[1] = 0;
			f(id, 0, 1) foreach(it2, ins[id]) if(contain(*it2, tuo->first)){
				tuo->root = false; ++height[id];
			}
			if(height[0] || height[1]) children.push_back(PTP(tuo, PII(height[0], height[1])));
		}
	}
	inline void dfs(){
		foreach(it, children) it->first->dfs();
		int base[2]; base[0] = base[1] = 0;
		f(id, 0, 1){
			std::sort(ins[id].begin(), ins[id].end(), bylen);
			int size = ins[id].size();
			int tmpdp[508]; memset(tmpdp, 0, sizeof(tmpdp));
			g(i, 0, size){
				tmpdp[i] = 0;
				g(j, 0, i) if(contain(ins[id][i], ins[id][j]) && tmpdp[j] > tmpdp[i]) tmpdp[i] = tmpdp[j];
				++tmpdp[i];
				if(tmpdp[i] > base[id]) base[id] = tmpdp[i];
			}
		}
		f(id, 0, 1){
			f(i, 0, n){
				if(i >= base[id]) dp[id][i] = base[!id]; else dp[id][i] = INF;
				foreach(it, children){
					Tuo *tuo = it->first; int a[2];
					a[0] = it->second.first; a[1] = it->second.second;
					if(i >= a[id]){
						int cans =tuo->dp[id][i - a[id]] + a[!id];
						if(cans > dp[id][i]) dp[id][i] = cans;
					}
				}
			}
			g(i, 0, n) if(dp[id][i] < dp[id][i + 1]) dp[id][i + 1] = dp[id][i];
		}
		f(id, 0, 1){
			int lt = INF, l2 = n;
			f(i, 0, n) if(dp[id][i] != lt){
				lt = dp[id][i];
				while(l2 >= lt) dp[!id][l2--] = i;
			}
		}
		f(i, 0, n) dp[0][i] = dp[1][i] = std::min(dp[0][i], dp[1][i]);
	}
};
inline bool cmp(Tuo *x, Tuo *y){
	return x->len < y->len;
}

int main(){
	int ___; scanf("%d", &___);
	f(__, 1, ___){
		memset(col, 0xff, sizeof(col));
		S.clear(); cn = 0;
		foreach(tuostar, tuos) delete *tuostar;
		tuos.clear();
		scanf("%d", &n);
		f(i, 1, n << 1){
			int &tar = S[gg()];
			if(tar){
				inv[++cn] = PII(tar, i);
			}else tar = i;
		}
		try{
			f(i, 1, n) if(col[i] == -1){
				Tuo *tuo = new Tuo;
				tuo->dfs(i, 0);
				tuos.push_back(tuo);
			}
			std::sort(tuos.begin(), tuos.end(), cmp);
			foreach(tuostar, tuos) (*tuostar)->findChildren();
			foreach(tuostar, tuos){
				Tuo *tuo = (*tuostar);
				if(tuo->root) tuo->dfs();
			}
			int bans = INF;
			f(top, 0, n){
				int cans = 0;
				foreach(tuostar, tuos){
					Tuo *tuo = (*tuostar);
					if(tuo->root){
						int cc = std::min(tuo->dp[0][top], tuo->dp[1][top]);
						if(cc > cans) cans = cc;
					}
				}
				cans += top;
				if(cans < bans) bans = cans;
			}
			printf("Case #%d: %d\n", __, bans);
		}catch(int){
			printf("Case #%d: -1\n", __);
		}
	}
	return 0;
}
  评论这张
 
阅读(231)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018