题目链接

loj#2071. 「JSOI2016」最佳团体
题解

树形dp强行01分规
代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gc getchar()

#define pc putchar

inline 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 2

1000 1 0

1 1000 1

*/
巴特西

loj#2071. 「JSOI2016」最佳团体

题目链接

题解

代码

最新文章

热门文章
