CF 814D

96 阅读 0 评论 64 点赞

我是靠谱客的博主稳重朋友，最近开发中收集的这篇文章主要介绍CF 814D，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这个题的DP做法感觉好神奇...

容易发现圆的包含关系是一个森林，我们设计状态是F[i][0/1][0/1]表示以i为根的子树中，第一个集合有偶数/奇数个圆包含它，第二个集合有偶数/奇数个圆包含它时能取得的最大权值，那么我们就可以比较容易的转移了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<vector>
 6 using namespace std;
 7 #define maxn 1005
 8 typedef long long LL;
 9 struct Vergil
10 {
11
int x,y,r;
12 }t[maxn];
13 int n,father[maxn];
14 LL f[maxn][2][2],ans;
15 vector<int> son[maxn];
16
17 LL dist(int o1,int o2)
18 {
19
return (LL)(t[o1].x-t[o2].x)*(t[o1].x-t[o2].x)+(LL)(t[o1].y-t[o2].y)*(t[o1].y-t[o2].y);
20 }
21
22 inline bool bh(int o1,int o2)
23 {
24
return dist(o1,o2)<(LL)t[o1].r*t[o1].r;
25 }
26
27 void dfs(int u)
28 {
29
int siz=son[u].size();
30
LL g[2][2]={{0}};
31
for (int i=0;i<siz;i++)
32 
{
33
int v=son[u][i];
34 
dfs(v);
35
for (int j=0;j<2;j++)
36
for (int k=0;k<2;k++)
37
g[j][k]+=f[v][j][k];
38 
}
39
LL w=(LL)t[u].r*t[u].r;
40
for (int i=0;i<2;i++)
41
for (int j=0;j<2;j++)
42
f[u][i][j]=max(g[i^1][j]+w*(i==0?1:-1),g[i][j^1]+w*(j==0?1:-1));
43 }
44
45 int main()
46 {
47
scanf("%d",&n);
48
for (int i=1;i<=n;i++) scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].r);
49
for (int i=1;i<=n;i++)
50
for (int j=1;j<=n;j++)
51 
{
52
if (t[j].r<=t[i].r) continue;
53
if (!bh(j,i)) continue;
54
if (!father[i]||t[father[i]].r>t[j].r) father[i]=j;
55 
}
56
for (int i=1;i<=n;i++)
57
if (father[i]) son[father[i]].push_back(i);
58
for (int i=1;i<=n;i++)
59
if (!father[i])
60 
{
61 
dfs(i);
62
ans+=f[i][0][0];
63 
}
64
printf("%.10fn",ans*acos(-1));
65
return 0;
66 }