题目链接
loj#2071. 「JSOI2016」最佳团体
题解
树形dp强行01分规
代码
#include<cstdio> #include<cstring> #include<algorithm>#define gc getchar() #define pc putcharinline int read() { ????int x = 0,f = 1; ????char c = gc; ????while(c < '0' || c > '9') c = gc; ????while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); ????return x * f; } void print(int x) { ????if(x < 0) { ????????pc('-'); ????????x = -x; ????} ????if(x >= 10) print(x / 10); ????pc(x % 10 + '0') ;} #define eps 1e-3 const int maxn = 2505; struct node { ????int next,v; } edge[maxn << 1]; int head[maxn], num = 0; void add_edge(int x,int v) { ????edge[++ num].v = v; ????edge[num].next = head[x]; ????head[x] = num; } int n,k ; double ans = -1.000; int s[maxn],p[maxn],siz[maxn]; double val[maxn]; double dp[maxn][maxn]; double tmp[maxn]; void dfs(int x,int fa) { ????siz[x] = 0; ????dp[x][0] = 0.0; ????for(int i = head[x];i;i = edge[i].next) { ????????int v = edge[i].v; ????????if(v == fa) continue; ????????dfs(v,x); ????????for(int j = 0;j <= siz[x] + siz[v];++ j) tmp[j] = -74123423432.123; ?????????for(int j = 0;j <= siz[x];++ j) { ????????????for(int k = 0;k <= siz[v]; ++ k) { ????????????????tmp[k + j] = std::max(tmp[k + j], dp[x][j] + dp[v][k]); ????????????} ????????} ????????siz[x] += siz[v]; ????????for(int i = 0;i <= siz[x];++ i) dp[x][i] = tmp[i]; ????} ????++ siz[x]; ????for(int i = siz[x];i >= 1;-- i) dp[x][i] = dp[x][i - 1] + val[x]; } bool check(double mid) { ????for(int i = 0;i <= n;++ i) ????????val[i] = 1.0 * p[i] - 1.0 * mid * s[i]; ????dfs(0,0); ????return dp[0][k + 1] >= 0.0; } int main() { ????//freopen("team0.in","r",stdin); ????k = read(),n = read(); ????for(int fa,i = 1;i <= n;++ i) { ????????s[i] = read(),p[i] = read(),fa = read(); ????????add_edge(fa,i); add_edge(i,fa); ????} ????double l = 0,r = 1000.0; ????int cnt = 30 ; ????while(cnt --) { ????????double mid = (r + l) / 2.0; ????????if(check(mid)) ans = mid,l = mid; ???????else r = mid; ????} ????printf ("%.3lf\n",l); ?????return 0; ???} /* 1 21000 1 01 1000 1*/loj#2071. 「JSOI2016」最佳团体
原文地址：https://www.cnblogs.com/sssy/p/9737795.html