题解 CF814D 【An overnight dance in discotheque】
皎月半洒花
2019-03-16 19:02:16
恶意评分成了一道黑题……本来应该是蓝色的啊$\rm{qaq}$
首先是奇怪的贪心，不过好像很合理的样子。大概就是一定要分成两堆的话，另一堆一定要放这一堆会冲突的圆。那么只需要记录覆盖层数的奇偶性，贪心地取就好了……
不过我是不敢在罚时的比赛里面随便交贪心，于是考虑一个$DP$。我们将之写作一个森林的形式，其中每棵树从上至下保持着半径的小根堆性质，且儿子一定会被父亲包含。那么在某棵树上，就一定有奇数层的贡献为$-1$,偶数层的贡献为$1$。
考虑用$dp[u][0/1][0/1]$表示以点$u$为根的子树里面，分成两堆之后，两堆分别的高度为偶数/奇数时的最优值。转移的时候从下向上$DP$，分类讨论一下就完了。
此处笔者选用的是官方题解里面比较优美的转移版本并且很闲地写了两个$sol$……
```cpp
#define MAXN 3050
using namespace std ;
const double Pi = acos(-1.0) ;
struct C{
double x, y, r ;
}base[MAXN] ;
double Ans ;
int i, j, k ;
long long dp[MAXN][2][2] ;
int N, mark[MAXN], fa[MAXN] ;
inline double dist(C A, C B){
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ;
}
inline double get_S(C A){ return Pi * A.r * A.r ; }
inline bool check_in(C A, C B){ return A.r + B.r > dist(A, B) ; }
namespace DP{
#define to(k) E[k].to
struct Edge{
int next, to ;
}E[MAXN << 1] ;
int head[MAXN], cnt ;
inline void Add(int u, int v){
E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].next = head[v], head[v] = cnt ;
}
void do_dp(int u, int faa){
long long f[2][2] ; memset(f, 0, sizeof(f)) ;
for (int k = head[u] ; k ; k = E[k].next){
if (to(k) == faa) continue ;
do_dp(to(k), u) ;
for (int ii = 0 ; ii <= 1 ; ++ ii)
for (int jj = 0 ; jj <= 1 ; ++ jj)
f[ii][jj] += dp[to(k)][ii][jj] ;
}
for (int ii = 0 ; ii <= 1 ; ++ ii)
for (int jj = 0 ; jj <= 1 ; ++ jj)
dp[u][ii][jj] = max(f[ii ^ 1][jj] + (1ll * (ii ? -1 : 1) * base[u].r * base[u].r),
f[ii][jj ^ 1] + (1ll * (jj ? -1 : 1) * base[u].r * base[u].r)) ;
}
inline bool Comp(C A, C B){
return A.r > B.r ; }
void solve1(){
sort(base + 1, base + N + 1, Comp) ;
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j)
if (check_in(base[i], base[j]))
if (!fa[j] || base[fa[j]].r > base[i].r) fa[j] = i ;
for (i = 1 ; i <= N ; ++ i) if (fa[i]) Add(i, fa[i]) ;
for (i = 1 ; i <= N ; ++ i) if (!fa[i]) do_dp(i, 0), Ans += dp[i][0][0] ;
printf("%.8lf", Ans * Pi) ;
}
}
namespace Greedy{
inline bool Comp(C A, C B){ return A.r > B.r ; }
void solve2(){
sort(base + 1, base + N + 1, Comp) ;
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j)
if (check_in(base[i], base[j])) ++ mark[j] ;
for (i = 1 ; i <= N ; ++ i)
if (!mark[i] || (mark[i] & 1)) Ans += get_S(base[i]) ; else Ans -= get_S(base[i]) ;
printf("%.8lf", Ans) ;
}
}
int main(){
cin >> N ;
for (i = 1 ; i <= N ; ++ i)
scanf("%lf%lf%lf", &base[i].x, &base[i].y, &base[i].r) ;
if (N >= 500) DP :: solve1() ; else Greedy :: solve2() ; return 0 ;
}
```