Codeforces Round #418 (Div. 2) D. An overnight dance in discotheque 题解

圆由于没有相交，之间的关系要么毫无关系，要么就是包含，所以能形成树。直接包含的就是父节点。

如果只有一组，不分前半夜后半夜的话，那么舒适度就是每棵树的根节点(深度为0)面积 - 深度为1的面积 + 深度为2的面积 ...

现在把每棵树分成2组，用DP来考虑到底这个结点是分到第1组还是第2组。

\(f[u][p1][p2]\) 表示假设结点 \(u\) 有 \(p1\) 个祖先在第1组，有 \(p2\) 个祖先在第2组时，舒适度的最大值。
显然以 \(u\) 为根节点的子树的舒适度的最大值为 \(f[u][0][0]\)。

状态计算如下

当 \(p1 \% 2 = 0\) ， 即 \(u\) 的深度为偶数时，说明 \(u\) 结点放在第1组里是要加上的，当 \(p1 \% 2 = 1\) 即 \(u\) 的深度为奇数时，说明 \(u\) 结点放在第1组里是要减去的。

叶子结点(边界)的 \(f[u][p1][p2]\) 就是直接加上自己的面积与直接减去自己的面积取最大值。而非叶子结点则需要把所有子树的值先统计起来，再分别与自己的面积相加或相减。

当 \(p1=0, p2=0\) 时，说明在2组内都应加上面积。

当 \(p1=0, p2=1\) 时，说明在第1组内应加上面积，第2组内应减去面积。

当 \(p1=1, p2=0\) 时，说明在第2组内应加上面积，第1组内应减去面积。

当 \(p1=1, p2=1\) 时，说明在2组内都应减去面积。

这样计算出结点 \(u\) 的 \(4\) 种情况。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
using ll = long long;
using Cir = struct _circle{
    int x, y, r;
};

const double pi = acos(-1.0);
const int N = 1010;
Cir a[N];
int n, p[N];
vector<int> e[N];
ll f[N][2][2];

// 求2个圆是否有包含关系
bool contain(int i, int j){
    return (ll)(a[i].x-a[j].x)*(a[i].x-a[j].x) + (ll)(a[i].y-a[j].y)*(a[i].y-a[j].y)
         <= (ll)(a[i].r-a[j].r)*(a[i].r-a[j].r);
}

void dfs_dp(int u){
    vector<vector<ll>> g(2, vector<ll>(2, 0));

    for(int i=0; i<e[u].size(); i++){
        int j = e[u][i];
        dfs_dp(j);
        for(int x=0; x<2; x++)
            for(int y=0; y<2; y++)
                g[x][y] += f[j][x][y];
    }

    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            f[u][i][j] = max(
                g[i^1][j] + (ll)a[u].r*a[u].r * (i==0 ? 1 : -1),
                g[i][j^1] + (ll)a[u].r*a[u].r * (j==0 ? 1 : -1)
            );
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x, y, r;
        scanf("%d%d%d", &x, &y, &r);
        a[i] = {x, y, r};
    }

    // 建树
    for(int i=1; i<=n; i++){
        p[i] = -1;
        for(int j=1; j<=n; j++){
            if(a[j].r > a[i].r && contain(i, j))
                if(p[i] == -1 || (a[p[i]].r > a[j].r))
                    p[i] = j;
        }
        if(p[i] != -1) e[p[i]].push_back(i);
    }

    // 可能不止一棵树
    ll res = 0;
    for(int i=1; i<=n; i++)
        if(p[i] == -1){
            dfs_dp(i);
            res += f[i][0][0];
        }

    printf("%.8lf\n", (double)res*pi);
    return 0;
}