Dで配点の割に手間取った。
http://codeforces.com/contest/814/problem/D
問題
2次元座標上でN個の円がある。各円の境界は互いに交差しない。
各円を2つのグループに分ける。両グループに関し、奇数個の円で囲まれた領域の面積の総和の最大値を求めよ。
解法
まず円の包含関係を森として表し、木DPをする。
f(c,mask) := 円cの領域が、両グループですでに囲まれているかどうかがmaskであらわされているときの円cの内部の面積の最大値
cをすでに奇数個の円で囲まれたグループに属させる場合、cの面積は減算されることになる。
それを踏まえて各円どちらのグループに属させた方が面積が最大になるかを子から(小さい円から)求めていこう。
int N; ll X[1010],Y[1010],R[1010]; double S[1010]; double memo[1010][4]; int P[1010]; vector<int> E[1010]; double dfs(int cur,int mask) { if(memo[cur][mask]==0) { if(mask==0) { memo[cur][mask]=S[cur]; FORR(e,E[cur]) memo[cur][mask] += dfs(e,1); } else if(mask==3) { memo[cur][mask]=-S[cur]; FORR(e,E[cur]) memo[cur][mask] += dfs(e,1); } else { double a=S[cur],b=-S[cur]; FORR(e,E[cur]) a += dfs(e,3); FORR(e,E[cur]) b += dfs(e,0); memo[cur][mask] = max(a,b); } } return memo[cur][mask]; } void solve() { int i,j,k,l,r,x,y; string s; double pi=atan(1)*4; cin>>N; FOR(i,N) { cin>>X[i]>>Y[i]>>R[i]; S[i]=pi*R[i]*R[i]; } FOR(i,N) { P[i]=-1; FOR(j,N) if(R[j]>R[i] && (X[j]-X[i])*(X[j]-X[i])+(Y[j]-Y[i])*(Y[j]-Y[i])<=R[j]*R[j]) { if(P[i]==-1 || R[j]<R[P[i]]) P[i]=j; } if(P[i]!=-1) E[P[i]].push_back(i); } double ret=0; FOR(i,N) if(P[i]==-1) ret+=dfs(i,0); _P("%.12lf\n",ret); }
まとめ
子側から求めようとして混乱してしまった。
親側で何個囲まれてるか考えるのだから、親から囲んだ数の偶奇を伝搬させればシンプルだったね。