# 4.9 省选模拟赛 圆圈游戏 树形dp set优化建图

``````const int MAXN=100010;
int n,m,len;
struct wy
{
ll x,y,r,w;
inline int friend operator <(wy a,wy b){return a.r<b.r;}
}t[MAXN];
int f[MAXN];
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
inline db dist(int x,int y){return sqrt((pf(t[x].x-t[y].x)+pf(t[x].y-t[y].y))*1.0);}
inline void dp(int x)
{
f[x]=t[x].w;
int sum=0;
go(x)
{
dp(tn);
sum+=f[tn];
}
f[x]=max(f[x],sum);
}
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
}
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
get(n);
rep(1,n,i)
{
ll x,y,r,w;
get(x);get(y);
get(r);get(w);
t[i]=(wy){x,y,r,w};
}
sort(t+1,t+1+n);
rep(1,n,i)//对于每个i找到一个最小的j.
{
db minn=INF;int p=0;
rep(i+1,n,j)
{
db d=dist(i,j);
if(t[j].r-t[i].r-d<0)continue;
if(t[j].r-t[i].r-d<minn)
{
minn=t[j].r-t[i].r-d;
p=j;
}
}
}
dp(0);put(f[0]);return 0;
}
``````

``````const ll MAXN=200010,maxn=3000010;
ll n,T,cnt,len;
ll f[MAXN];
ll lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
struct wy{ll x,y,z,r,id;}t[MAXN];
struct jl{ll x,y,op;}q[MAXN];
inline ll cmp(jl a,jl b){return a.x<b.x;}
inline void dp(ll x)
{
f[x]=t[x].z;
ll sum=0;
go(x)
{
dp(tn);
sum+=f[tn];
}
f[x]=max(f[x],sum);
}
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
}
struct data
{
ll id,op;
//data(){};
inline double calc()const
{
if(op)return t[id].y+sqrt((pf(t[id].r)-pf(t[id].x-T))*1.0);
return t[id].y-sqrt((pf(t[id].r)-pf(t[id].x-T))*1.0);
}
inline ll friend operator <(data a,data b)
{
double x=a.calc();db y=b.calc();
if(fabs(y-x)>EPS)return x<y;
if(a.op!=b.op)return a.op<b.op;
return a.id<b.id;
}
};
set<data>s;
set<data>::iterator it;
signed main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
get(n);
rep(1,n,i)
{
ll x,y,z,r;
get(x);get(y);get(r);get(z);
t[i]=(wy){x,y,z,r};
q[++cnt]=(jl){t[i].x-t[i].r,i,1};
q[++cnt]=(jl){t[i].x+t[i].r,i,-1};
}
sort(q+1,q+1+cnt,cmp);
//rep(1,cnt,i)cout<<q[i].y<<endl;
rep(1,cnt,i)
{
T=q[i].x;
//cout<<(*s.begin()).id<<‘ ‘<<(*s.begin()).op<<endl;
if(q[i].op==1)
{
s.insert((data){q[i].y,1});
it=s.find((data){q[i].y,1});
++it;
if(it==s.end())f[q[i].y]=0;
else
{
if((*it).op==0)f[q[i].y]=f[(*it).id];
else f[q[i].y]=(*it).id;
}
s.insert((data){q[i].y,0});
}
else
{
s.erase((data){q[i].y,1});
s.erase((data){q[i].y,0});
}
}
dp(0);put(f[0]);return 0;
}
``````

## P2016 战略游戏——树形DP大水题

P2016 战略游戏 树形DP 入门题吧(现在怎么是蓝色标签搞不懂): 注意是看见每一条边而不是每一个点(因为这里错了好几次): #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=3010; int pre[maxn],last[maxn],other[maxn],l; void add(int x,int y) { l++; pre[l]