[JSOI2016]最佳团体 DFS序/树形DP

题目

Description

茜茜的舞蹈团队一共有\(N\)名候选人，这些候选人从\(1\)到\(N\)编号。方便起见，茜茜的编号是\(0\)号。每个候选人都由一位编号比他小的候选人\(R_i\)推荐。如果\(R_i=0\)则说明这个候选人是茜茜自己看上的。为了保证团队的和谐，茜茜需要保证，如果招募了候选人\(i\)，那么候选人\(R_i\)也一定需要在团队中。当然了，茜茜自己总是在团队里的。每一个候选人都有一个能力值\(P_i\)，也有一个招募费用\(S_i\)。茜茜希望招募\(K\)个候选人（茜茜自己不算），组成一个性价比最高的团队。也就是，这\(K\)个被茜茜选择的候选人的总能力值与总招募总费用的比值最大。

Input

输入一行包含两个正整数\(K\)和\(N\)。

接下来\(N\)行，其中第\(i\)行包含\(3\)个整数\(S_i\),\(P_i\),\(R_i\)表示候选人\(i\)的招募费用，战斗值和推荐人编号。

Output

输出一行一个实数，表示最佳比值。答案保留三位小数。

Sample Input 1

1 2
1000 1 0
1 1000 1

Sample Output 1

0.001

Hint

对于\(100\%\)的数据满足\(1\le K\le N\le 2500, 0<S_i,P_i≤10^4 ,0 ≤R_i <i\).

思路 0/1分数规划+树形DP

几乎是裸的0/1分数规划,于是二分答案,问题转化为与选课一模一样的树上背包问题,可以用树形DP在\(O(nk^2)\)的时间复杂度内求解.

可是我们定睛一看,\(1\le K\le N\le 2500\).

所以\(O(nk^2)\)的复杂度是无法接受的.

这时我们想到,在洛谷P2014 选课 题解中,有许多大佬提到可以通过在DFS序上DP的方法,把一次树形DP的时间复杂度降为\(O(nk)\).但是我不会啊??.于是考试的时候想了\(\inf\)秒,还是没有想出来.然后就交了\(O(nk^2log\text{ SIZE})\)的算法,得到了\(45\)分的好成绩.

然后我就去学了在DFS序上DP的方法,原来是这样的:

用一次 DFS 求出树的 DFS 序以及每个节点的子树大小 \(Siz(u)\),按 DFS 序从后往前 DP ,有:

\[DP[i,j]=\max (DP[i+1,j-1]+P[i],DP[i+Siz(i),j])\]

这个状态转移方程的含义是,如果选择当前候选人,那么考虑继续选择DFS序排在他后面的候选人,并且累计当前候选人的权值,即\(DP[i+1,j-1]+P[i]\).如果不选当前的人,则子孙节点一定不选,直接跳过,即\(DP[i+Siz(i),j]\).

#include<bits/stdc++.h>
const int SIZE=2505;
const double eps=1e-5;
int n,m,P[SIZE],S[SIZE];
double G[SIZE],DP[SIZE][SIZE]; 
int head[SIZE],nex[SIZE],to[SIZE],Tot;
void Link(int u,int v){nex[++Tot]=head[u];head[u]=Tot;to[Tot]=v;}

int In()
{
    char ch=getchar();
    int x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return x;
}

int DFN[SIZE],Siz[SIZE],Tim;
void DFS(int u)
{
    DFN[++Tim]=u;
    Siz[u]=1;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];
        DFS(v);
        Siz[u]+=Siz[v];
    }
}

bool Check(double Mid)
{
    memset(DP,0xC2,sizeof(DP));
    for(int i=0;i<=n;i++)
        G[i]=(double)P[i]-Mid*S[i];
    DP[n+2][0]=0; 
    for(int i=n+1;i;i--)
    {
        int u=DFN[i];
        for(int k=0;k<=m;k++)
            DP[i][k]=std::max(DP[i+Siz[u]][k],DP[i+1][k-1]+G[u]);
    }
    return DP[1][m]>0; 
}

int main()
{
    scanf("%d%d",&m,&n);
    ++m;
    for(int i=1;i<=n;i++)
    {
        S[i]=In();
        P[i]=In();
        Link(In(),i);
    }
    DFS(0);
    double L=0,R=1e4,Ans;
    while(R-L>eps)
    {
        double Mid=(L+R)/2;
        if(Check(Mid))
        {
            Ans=Mid;
            L=Mid;
        }
        else R=Mid;
    }
    printf("%.3lf",Ans);
    return 0;
}

附:考试时写的\(O(nk^2log\text{ SIZE})\)的暴力,洛谷上有人说如果把DFS过程中每个点的转移循环的上界改成$Siz(u) \(,时间复杂度也是\)O(n^2)$的.不过我也不大会证明.

#include<bits/stdc++.h>
const int SIZE=2505;
const double eps=1e-5;
int n,m,F[SIZE],P[SIZE],S[SIZE];
double G[SIZE],DP[SIZE][SIZE]; 
int head[SIZE],nex[SIZE],to[SIZE],Tot;

inline int In()
{
    char ch=getchar();
    int x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return x;
}

inline void Link(int u,int v)
{
    nex[++Tot]=head[u];head[u]=Tot;to[Tot]=v;
}

void DFS(int u)
{
    for(register int i=head[u];i;i=nex[i])
    {
        int v=to[i];
        DFS(v);
        for(int j=m;j;j--)
            for(int k=0;k<j;k++)
                DP[u][j]=std::max(DP[u][j],DP[u][j-k]+DP[v][k]);
    }
}

bool Check(double Mid)
{
    for(register int i=0;i<=n;i++)
    {
        for(register int k=0;k<=m;k++)
            DP[i][k]=-1e9;
        DP[i][1]=(double)P[i]-Mid*S[i];
    }   
    DFS(0);
    return DP[0][m]>0; 
}

int main()
{
    freopen("team.in","r",stdin);
    freopen("team.out","w",stdout);
    scanf("%d%d",&m,&n);
    ++m;
    for(register int i=1;i<=n;i++)
    {
        S[i]=In();
        P[i]=In();
        Link(In(),i);
    }
    double L=0,R=1e4,Ans;
    while(R-L>eps)
    {
        double Mid=(L+R)/2;
        if(Check(Mid))
        {
            Ans=Mid;
            L=Mid;
        }
        else R=Mid;
    }
    printf("%.3lf",Ans);
    return 0;
}

[JSOI2016]最佳团体 DFS序/树形DP

原文：https://www.cnblogs.com/TaylorSwift13/p/11772087.html