Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities（贪心）

题目链接：http://codeforces.com/contest/962/problem/E

我可能是个弱智

直接贪心，B和R的连发比较固定，考虑每个P，他有两种选择，一种是连接到上一个P上然后删掉B和R的最大值，一种是直接连到上一个B和R上，直接模拟就行了

代码：

	ll ans=0;
	int n;
	int pa=INF,pb=INF,pc=INF,pra=0,prb=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		char op[2];
		scanf("%d%s",&x,op);
		if(op[0]=='B')
		{
			if(pa!=INF)
			{
				pra=max(pra,x-pa);
				ans+=x-pa;
			}
			pa=x;
		}
		if(op[0]=='R')
		{
			if(pb!=INF)
			{
				prb=max(prb,x-pb);
				ans+=x-pb;
			}
			pb=x;
		}
		if(op[0]=='P')
		{
			if(pa!=INF)
			{
				pra=max(pra,x-pa);
				ans+=x-pa;
			}
			if(pb!=INF)
			{
				prb=max(prb,x-pb);
				ans+=x-pb;
			}
			if(pc!=INF)
			{
				ans=min(ans,ans+x-pc-pra-prb);
			}
			pa=pb=pc=x;
			pra=prb=0;
		}
	}
	printf("%lldn",ans);
	return 0;
}

最后

以上就是无奈橘子最近收集整理的关于Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities（贪心）的全部内容，更多相关Educational内容请搜索靠谱客的其他文章。