【BZOJ5281】Talent Show（分数规划）

时间：2023-03-09 16:15:51
【BZOJ5281】Talent Show（分数规划）

【BZOJ5281】Talent Show（分数规划）

题面

BZOJ

洛谷

题解

二分答案直接就是裸的分数规划，直接跑背包判断是否可行即可。

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

#define MAX 255

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,W,w[MAX],t[MAX];

double s[MAX],f[MAX][1010];

void upd(double &x,double y){if(x<y)x=y;}

int main()

{

	n=read();W=read();

	for(int i=1;i<=n;++i)

		w[i]=read(),t[i]=read();

	double l=0,r=10000;

	while(r-l>1e-5)

	{

		double mid=(l+r)/2;

		for(int i=1;i<=n;++i)s[i]=t[i]-mid*w[i];

		for(int i=0;i<=n;++i)

			for(int j=0;j<=W;++j)

				f[i][j]=-1e18;

		f[0][0]=0;

		for(int i=1;i<=n;++i)

			for(int j=0;j<=W;++j)

			{

				upd(f[i][j],f[i-1][j]);

				upd(f[i][min(W,j+w[i])],f[i-1][j]+s[i]);

			}

		if(f[n][W]>=0)l=mid;

		else r=mid;

	}

	int ans=l*1000;

	printf("%d\n",ans);

	return 0;

}

相关文章