本文最后更新于:2020年4月20日 晚上

题目来源NAIPC 2016 或 [Jsoi2016]最佳团体,你会发现这俩题完全一致…

(听说是那段时间jsoi就是汉化国外的题目)

题目链接:http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006280

或https://nanti.jisuanke.com/t/A2026

或https://www.lydsy.com/JudgeOnline/problem.php?id=4753

题意是说有n+1n+1个人,00号是CEO,11nn号是参选员工,每个员工ii给一个薪水ss和生产力pp,还有一个推荐他的人的编号r(0r<i)r(0\le r < i),现在要选出kk个员工,如果选了某个员工那么他的推荐人也必须选(除非他的推荐人是CEO),使得选出kk个员工的生产力之和除以薪水之和最大。

做法:n+1n+1个人实际构成了一个树,CEO是根。首先01分数规划模型很显然,那么二分答案midmid,新的点权为pisi×midp_i-s_i\times mid,现在要求树上k+1k+1个点的连通块(包括根)的最大点权和。

经典背包型dp,dp[i][j]dp[i][j]表示以ii为根的联通块大小为jj的最大点权和,最后求出dp[0][k+1]dp[0][k+1]小于00说明二分出来的值比答案大了,反之说明小了。

直观上看二维的状态,转移还需要枚举新加的一个子树选多少的点,这样似乎上是O(N3)O(N^3),会超时?

实际上,我们每次只for到子树大小,可以证明这样时间复杂度是O(N2)O(N^2)。直接看图理解吧:

意思就是说这样的写法等价于枚举所有的点对(x,y)(x,y)的时间。所以最终这道题的时间复杂度为O(N2logC)O(N^2\log{C})

#include<bits/stdc++.h>
using namespace std;
#define N 2550
const double INF=1e99;
int k,n;
int num[N],a[N],b[N];
double dp[N][N],c[N],now[N];
vector<int> e[N];

void dfs(int u,int f)
{
    double tmp[N];
    tmp[0]=c[u];
    num[u]=0;
    for(auto &v:e[u])
    {
        if(v==f)continue;
        dfs(v,u);
        for(int i=0;i<=num[u]+num[v];i++)
            now[i]=-INF;
        for(int i=0;i<=num[u];i++)
            for(int j=0;j<=num[v];j++)
                now[i+j]=max(now[i+j],tmp[i]+dp[v][j]);
        for(int i=0;i<=num[u]+num[v];i++)
            tmp[i]=now[i];
        num[u]+=num[v];
    }
    num[u]++;
    dp[u][0]=0;
    for(int i=1;i<=num[u];i++)
        dp[u][i]=tmp[i-1];
}
double calc(double mid)
{
    c[0]=0;
    for(int i=1;i<=n;++i) c[i]=a[i]-mid*b[i];
    dfs(0,-1);
    return dp[0][k+1];
}
int main()
{
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;++i)
    {
        int fa;
        scanf("%d%d%d",b+i,a+i,&fa);
        e[fa].push_back(i);
    }
    double l=0,r=10000;
    for(int i=1;i<=50;++i)
    {
        double mid=(l+r)/2;
        if(calc(mid)>=0) l=mid;
        else r=mid;
    }
    printf("%.3f\n",l);
    return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

Hello World 上一篇
Burnside引理与Polya计数公式 下一篇