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

本文主要是介绍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("%lld\n",ans);return 0;
}

这篇关于Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---