CF962E

CF962E

题意:让你给点连线，再去除所有R点，或B点后都可以实现任意两点互相可达，并且代价最小，两点连线的代码为两点间的距离

题解：我只需要当到达P点的时候要么与前一个p点相连3次然后减取之前R点B点的最大两点距离，或者就直接与前面一个点连接两次取两者最小值即可，其他情况直接与前面一个点相连即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<stack>
#include<bitset>
using namespace std;
#define mes(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(i = a; i <= b; i++)
#define dec(i,a,b) for(i = b; i >= a; i--)
#define fi first
#define se second
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,L,mid
#define rson rs,mid+1,R
typedef double db;
typedef long long int ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const ll inf = 1e15;
const int mx = 2e5+5;
const int x_move[] = {1,-1,0,0,1,1,-1,-1};
const int y_move[] = {0,0,1,-1,1,-1,1,-1};
int main(){int t,q,ca = 1;int n;ll pa,pb,pc;ll ans = 0;pa = pb = pc = inf;ll pra = 0,prb = 0;scanf("%d",&n);for(int i = 0; i < n; i++){ll v;char str[10];scanf("%I64d%s",&v,str);if(str[0]=='R'){if(pa!=inf){pra = max(pra,v-pa);ans += v-pa;}pa = v;}else if(str[0]=='B'){if(pb!=inf){prb = max(prb,v-pb);ans += v-pb;}pb = v;}else{if(pb!=inf){prb = max(prb,v-pb);ans += v-pb;}if(pa!=inf){pra = max(pra,v-pa);ans += v-pa;}if(pc!=inf)ans = min(ans,ans+v-pc-pra-prb);pa = pb = pc = v;pra = prb = 0;}}printf("%I64dn",ans);return 0;
}