Preface

DP专题里终于有一道完全自己做出来且正确的题了。

Description

给你一棵树，每个结点有两个值产值与污染值，让你选出 $ N-M $ 个点，他们仍然是一棵树，且 $ \frac{\sum_{i=1}^{N-M} a_i}{\sum{i=1}^{N-M} b_i } $ 最大。

Method

Idea

我们如果直接处理这个式子的话，发现会有点棘手，因为答案与 $ a_i $ 的值和 $ b_i $ 的值都有关，我们无法判断究竟让 $ a_i $ 尽可能大还是 $ b_i $ ，所以我们考虑将这个式子转换成只与一个值有关，关于做这个，我们考虑二分答案

Dichomotous Answer

我们设答案为 $ x $ ,则式子变为 $ \frac{\sum_{i=1}^{N-M} a_i}{\sum{i=1}^{N-M} b_i }=x $ ，即\(\sum_{i=1}^{N-M} a_i=x*\sum_{i=1}^{N-M} b_i\),即\(\sum_{i=1}^{N-M} a_i-x*\sum_{i=1}^{N-M} b_i=0\),即\(\sum_{i=1}^{N-M} a_i-x*b_i=0\),那么我们只要判断最后的总和是否大于\(0\)即可，现在我们就把与答案合法性有关的数据框定在一个值内了，下面就是用DP去求出刚才那个式子的最大值就可以了。

DP

DP state transition equation

$ f_{i,j}=\max(f_{i,j},f_{i,j-k}+f_{son_i,k}) (0<=k<=j) $

$ f_{i,j}=f_{i,j-1}+value_i $

$ ans=\max{f_{i,n-m}} $

Explanation

$ f_{i,j} $ ---在以 $ i $ 为根的子树下选了 $ j $ 个且 $ i $ 一定选了所能达到的最大值。

$ f_{i,j-k}+f_{son_i,k} $ ---从下方的子树转移过来。

$ f_{i,j-1}+value_i $ ---强制选 $ i $

Code

#include<bits/stdc++.h>
using namespace std;
double f[1010][1010],e[100000];
int i,x,y,n,m,cnt;
double e1[100000],e2[100000];
int a[100100],b[100100],d[100100];
double l,r,mid,ans,sum;
void add(int x,int y)
{
	cnt++;a[cnt]=y;b[cnt]=d[x];d[x]=cnt;
}
void sc(int x,int fa)
{
	for (int i=d[x];i;i=b[i])
	    if (a[i]!=fa)
	        {
	        	sc(a[i],x);
	        	for (int k=m;k>0;k--)
	        	   for (int j=k;j>=0;j--)
	        	      f[x][k]=max(f[x][k],f[x][k-j]+f[a[i]][j]);
			}
   for (int i=m;i>=1;i--) f[x][i]=f[x][i-1]+e[x];
   sum=max(sum,f[x][m]);
}
bool check(double mid)
{
	int i,j;
	for (i=1;i<=n;i++) e[i]=e1[i]-mid*e2[i];
	for (i=1;i<=n;i++)
	    for (j=1;j<=m;j++)
	        f[i][j]=-1000000000;
	sum=-1;
    sc(1,0);
    return (sum>=0);
}
int main()
{
	cin>>n>>m;m=n-m;
	for (i=1;i<=n;i++) cin>>e1[i];
	for (i=1;i<=n;i++) cin>>e2[i];
	for (i=1;i<n;i++)
	     {
	     	cin>>x>>y;
	     	add(x,y);add(y,x);
		 }
	l=0;r=1000000;
	while (r-l>1e-4)
	      {
	      	mid=(l+r)/2;
	      	if (check(mid))
	      	     {
	      	     	ans=mid;l=mid;
				   }
		else r=mid;
		  }
	printf("%.1lf\n",ans);
	return 0;
}

LuoguP1642题解

原文：https://www.cnblogs.com/huangxuze/p/14708568.html