google code jam 2014 RC_C

一道很灵活的贪心小题木,我也是看了官方题解才想到的- -!!一般都用最大流做的。

枚举+贪心构造法

#include <cstdio>
#include <cstring>
using namespace std;int T,N;
char com[1001][2];
int id[1001];
bool in[5001];
bool oc[5001];
int sot[5001];
int ID=2001;bool simulate(int n){for(int i=0; i<n; ++i){bool sta=0;memset(oc,0,sizeof(oc));for(int j=0; j<N; ++j){if(com[j][0]=='L'&&oc[id[j]]==0&&id[j]&&in[id[j]]==0){in[id[j]]=1;sta=1;break;}oc[id[j]]=1;}if(sta==0){in[ID++]=1;}}for(int i=0; i<N; ++i){if(com[i][0]=='E'){if(id[i]==0){bool sta=0;memset(oc,0,sizeof(oc));for(int j=i+1; j<N; ++j){if(com[j][0]=='L'&&oc[id[j]]==0&&id[j]&&in