首页 > 代码库 > BZOJ 4753 二分+树形DP
BZOJ 4753 二分+树形DP
思路:
先二分答案
f[x][j]表示在x的子树里选j个点
f[x][j+k]=max(f[x][j+k],f[x][j]+f[v[i]][k]);
初始化
x!=0 -> f[x][1]=p[x]-s[x]*mid
x=0 -> f[x][0]=0
类似4033的那样转移 看似O(n^3)实际O(n^2)
加一个二分 复杂度O(能过)
//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=2505;int n,K,s[N],p[N],r[N],first[N],next[N],v[N],tot,size[N];double f[N][N],mid;void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x){ if(x){size[x]=1;f[x][1]=p[x]-s[x]*mid;} else size[0]=0,f[0][0]=0; for(int i=first[x];~i;i=next[i]){ dfs(v[i]); for(int j=size[x];j>=0;j--){ for(int k=size[v[i]];k>=0;k--){ f[x][j+k]=max(f[x][j+k],f[x][j]+f[v[i]][k]); } } size[x]+=size[v[i]]; }}int main(){ memset(first,-1,sizeof(first)); scanf("%d%d",&K,&n); for(int i=1;i<=n;i++){ scanf("%d%d%d",&s[i],&p[i],&r[i]); add(r[i],i); } double l=0,r=0x3f3f3f; while(r-l>1e-5){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j]=-0x3f3f3f; mid=(l+r)/2; dfs(0); if(f[0][K]>0)l=mid; else r=mid; } printf("%.3lf\n",l);}
BZOJ 4753 二分+树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。