menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[分数规划+树形DP]BZOJ4753(Jsoi2016)【最佳团体】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $n+1$ 个人,选第 $i$ 个人需要花费 $s_i$ ,得到 $p_i$ 的贡献,第一个人必选,没有花费和贡献。$2\sim n+1$ 都有一个推荐人(推荐人编号小于自己的编号),一个人选了就必须选推荐人,求最大性价比。

解题报告

先分数规划,然后转为树形DP。定义 $f[i][j]$ 表示 $i$ 子树中选了 $j$ 个人的最优解,瞎转移就行了。

注意转移时需要默认 $i$ 是必选的,所以 $f[i][0]$ 刚开始没有值,处理完树形背包之后再把 $f[i][0]$ 给 $0$(或者再开一个数组,没人拦着你)

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long double DB;
const int maxn=2500;

int K,n,w[maxn+5],p[maxn+5],si[maxn+5];DB P[maxn+5];
int E,lnk[maxn+5],nxt[maxn+5],son[maxn+5];DB f[maxn+5][maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void DP(int x){
    memset(f[x],254,sizeof(f[x]));f[x][1]=P[x];si[x]=1;
    for (int e=lnk[x],u;e;si[x]+=si[u],e=nxt[e])
        for (int j=(DP(u=son[e]),min(si[x]+si[u],K));j;j--)
            for (int i=max(j-si[x],0);i<j&&i<=si[u];i++) //这么写就O(n^2)啦
                f[x][j]=max(f[x][j],f[x][j-i]+f[u][i]);f[x][0]=0;
}
inline bool check(DB ans) {P[1]=0;for (int i=2;i<=n;i++) P[i]=p[i]-ans*w[i];DP(1);return f[1][K]>1e-8;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=2,fa=(scanf("%d%d",&K,&n),K++,n++);i<=n;i++)
        scanf("%d%d%d",&w[i],&p[i],&fa),Add(fa+1,i);
    DB L=0,R=25000000,mid;while (R-L>1e-5) check(mid=(L+R)/2)?L=mid:R=mid;
    return printf("%.3f\n",(double)L),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up