题解——gift（dfs序处理树上背包问题）

本题ssw02参考了蒋神的代码
模拟赛，蒋神在T1挂了的情况下依然两校区rank1

欢迎转载ssw02的博客：https://www.cnblogs.com/ssw02/p/11640828.html

题目

题面描述：一个带限制的树上背包问题

输入：一棵树+各种限制条件（属性）

输出：价值和消费比的最大值

思路

做这道题之前，先把这道题灭了再说[JSOI2016]最佳团体

先二分答案（01分数规划套路），然后一样处理出 val[ i ] = ( 价值 - mid × 花费 )

DP的转移方程有点不一样。由于有了人手至少一份和a[ i ]的限制，我们不妨考虑，dp[ i ][ j ]中的 j 值不再是选了 j 种物品，而是有j 个人已经获得了物品。

然后考虑转移的问题，我们先考虑这种情况：每个人都有了一份礼物，然后现在手中还有一些礼物。我们明显要最优值时，肯定可以将剩下的多余的物品再发给已有物品的人，这样就可以得到剩余的 val > 0 的物品的贡献值。
所以说 dp[ 一个状态 ][ M ] = dp[ 前一个状态 ][ M ]

同时我们考虑到，只有至少人手一份，才是一种合法的答案，为了尽可能快的达到人手一份的限制，我们肯定会在分一个物品时优先把这个物品分给没有拿到物品的人，这样可以让我们在选满后有更多的余地选择上述的更加优的物品。

简单举个例子：如果可以填满然而没有填满，例如还有 5 个人没有物品，但此时你有两件val为 5 ， -10 ，个数为 3 4 的物品，你无论如何都无法避免地选到val 为负值的物品，而填满的情况则可以自由选择。（ssw02只能口胡，感性分析正确性）

然后及时有树形依赖关系背包问题。

我们可以考虑使用树上背包的惯用做法 dp[ i ][ j ] 处理 i 子树中 j 个人有礼物。

也可以使用 dfs序将属性依赖关系转化到序列上。采用不选择就跳子树的操作.dp[ i ][ j ]表示处理dfs序 i 后 j 个人有礼物的情况。

代码

ssw02参考蒋神代码后选择了常数较小的dfs序DP写法，这种做法倒叙枚举和顺序枚举没有本质区别

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 1005 ;
inline int read(){
	int s=0 ; char g=getchar() ; while(g>'9'||g<'0')g=getchar() ;
	while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ;
}
int N , K ; 
double p[ MAXN ] , s[ MAXN ] , val[ MAXN ] , dp[ MAXN ][ MAXN ];
int  tot = 1 , spread[ MAXN ], head[ MAXN ] , to[ MAXN*2 ] , nex[ MAXN*2 ] ;
int  cnt = 0 , dfn[ MAXN ] , id[ MAXN ], size[ MAXN ] ;
void  add( int x , int y ){
	to[ ++tot ] = y , nex[ tot ] = head[ x ] , head[ x ] = tot ;
}
inline void  dfs( int u , int fa ){//从0开始只是因为树根为 0 ， 刨除贡献 
	dfn[ u ] = cnt , id[ cnt++ ] = u , size[ u ] = 1 ;
	for( int i = head[ u ] ; i ; i = nex[ i ] ){
		dfs( to[ i ] , u  ) ;
		size[ u ] += size[ to[ i ] ] ;
	}
	return ;
} 
inline bool check( double x ){
	for( int i = 1 ; i <= N ; ++i )val[ i ] = p[ i ] - x*s[ i ] ;
	dp[ N+1 ][ 0 ] = 0 ;
	for( int i = 1; i <= K ; ++i ) dp[ N+1 ][ i ] = -1e9 ;
	for( int i = N ; i > 0 ; --i ){
		int u = id[ i ];
		for( int j = 0 ; j <= K ; ++j ){
			dp[ i ][ j ] = dp[ i+size[ u ] ][ j ] ;
			if(j <= spread[u] ){
				if(dp[i+1][0]+val[u]>dp[i][j])
				{
					dp[i][j]=dp[i+1][0]+val[u];
				}
			}
			else
			{
				if(dp[i+1][j-spread[u]]+val[u]>dp[i][j])
				{
					dp[i][j]=dp[i+1][j-spread[u]]+val[u];
				}
			}
		}
	}
	return dp[ 1 ][ K ] >= 0 ;
}
/*错误代码
for( int i = 1 ; i <= N ; ++i )val[ i ] = p[ id[i] ] - x*s[ id[i] ] ;
	dp[ 0 ][ 0 ] = 0 ; 
	for( int j = 0 ; j <= K ; ++j )dp[ 0 ][ j ] = -1e8 ; 
	for( int i = 0 ; i <= N ; ++i )
	   for( int j = 0 ; j <= min( i , K ) ; ++j ){
	   	   if( j <= spread[ id[ i ] ] )
			  dp[ i+1 ][ j+1 ] = max( dp[ i+1 ][ j+1 ] , dp[ i ][ 0 ]+val[ i ] ) ;
	   	   else
	   	   	  dp[ i+1 ][ j+1 ] = max( dp[ i+1 ][ j+1 ] , dp[ i+1 ][ j-spread[ id[i] ]] + val[ i ] ) ;
		   dp[ i+size[ id[i] ] ][ j ] = max( dp[ i+size[ id[i] ] ][ j ] , dp[ i ][ j ] ) ;
	   }
	return dp[ N+1 ][ K ] >= 0 ;
*/
void  dx( double l , double r ){
	while( r - l > 0.0000001 ){
		double mid = ( l+r )/2.0 ;
		if( check(mid) )l = mid ; else r = mid ; 
	}
	printf("%0.10lf",l) ;
}
int main(){ 
    //freopen("gift.in","r",stdin);
    //freopen("gift.out","w",stdout);
	N = read() , K = read() ; int m1 , m2 , m3 ; double ma = -1.0 ;
	for( register int i = 1 ; i <= N ; ++i ){
		spread[ i ] = read() , p[ i ] = 1.0*read() , s[ i ] = 1.0*read() , m3 = read() ; 
		add( m3 , i ) ; 
	}
	dfs( 0 , 0 ) ;
	val[ 0 ] = 0.0 ;
	dx( (double)0 , 100000 ) ; 
	return 0 ;
}

如有不足，请各位指出。