P4377 [USACO18OPEN] Talent Show G
[P4377 USACO18OPEN] Talent Show G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
目录题目
题目描述
Farmer John 要带着他的 \(n\) 头奶牛,方便起见编号为 \(1\ldots n\),到农业展览会上去,参加每年的达牛秀!他的第 \(i\) 头奶牛重量为 \(w_i\),才艺水平为 \(t_i\),两者都是整数。
在到达时,Farmer John 就被今年达牛秀的新规则吓到了:
(一)参加比赛的一组奶牛必须总重量至少为 \(W\)(这是为了确保是强大的队伍在比赛,而不仅是强大的某头奶牛),并且。
(二)总才艺值与总重量的比值最大的一组获得胜利。
FJ 注意到他的所有奶牛的总重量不小于 \(W\),所以他能够派出符合规则(一)的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。
输入格式
第一行是两个整数,分别表示牛的个数 \(n\) 和总重量限制 \(W\)。
第 \(2\) 到 \((n+1)\) 行,每行两个整数,第 \((i + 1)\) 行的整数表示第 \(i\) 头奶牛的重量 \(w_i\) 和才艺水平 \(t_i\)。
输出格式
请求出 Farmer 用一组总重量最少为 \(W\) 的奶牛最大可能达到的总才艺值与总重量的比值。
如果你的答案是 \(A\),输出 \(1000A\) 向下取整的值,以使得输出是整数(当问题中的数不是一个整数的时候,向下取整操作在向下舍入到整数的时候去除所有小数部分)。
样例 #1
样例输入 #1
3 15
20 21
10 11
30 31
样例输出 #1
1066
提示
样例解释
在这个例子中,总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为 \(11\)、重量为 \(10\) 的奶牛,但是由于我们需要至少 \(15\) 单位的重量,最优解最终为使用这头奶牛加上才艺值为 \(21\)、重量为 \(20\) 的奶牛。这样的话才艺与重量的比值为 \(\frac{11+21}{10+20}=\frac{32}{30} = 1.0666\dots\),乘以1000向下取整之后得到 \(1066\)。
数据规模与约定
对于全部的测试点,保证 \(1 \leq n \leq 250\),\(1 \leq W \leq 1000\),\(1 \leq w_i \leq 10^6\),\(1 \leq t_i \leq 10^3\)。
思路
正解是01分数规划 + 背包
1、分数规划
二分答案
\[\sum \frac{t_i}{w_i} \geq mid \]即
\[\sum(t_i - mid * w_i) \geq 0 \]所以
\[p_i = t_i - mid * w_i \]2、背包
设 dp[i] 表示重量为 \(i\) 时可以取到 \(p\) 最大的值。
大于等于 \(W\) 的都存在 \(dp[W]\) 上,这个就是答案。
那么
\[dp[j + w[i]] = max (dp[j + w[i]] , dp[j] + c[i]) \]code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
#define LL long long
using namespace std;
const int N = 255 , M = 1005;
const double eps = 1e-6;
const int inf = 1e8 + 5;
int n , W;
double p[N] , dp[M];
LL w[N] , t[N] , st;
double ck () {
fu (i , 1 , W) dp[i] = -inf;
fu (i , 1 , n) {
fd (j , W , 0) {
if (j + w[i] >= W) dp[W] = max (dp[W] , dp[j] + p[i]);
else dp[j + w[i]] = max (dp[j + w[i]] , dp[j] + p[i]);
}
}
return dp[W];
}
double fans () {
double l = 0 , r = st , mid;
while (r - l > eps) {
mid = (l + r) / 2;
fu (i , 1 , n) p[i] = t[i] - w[i] * mid;
if (ck () >= eps) l = mid + eps;
else r = mid;
}
return l;
}
int main () {
scanf ("%d%d" , &n , &W);
fu (i , 1 , n)
scanf ("%lld%lld" , &w[i] , &t[i]) , st += t[i];
printf ("%lld" , (LL)(fans () * 1000));
return 0;
}
标签:Talent,样例,USACO18OPEN,P4377,mid,leq,奶牛,dp,才艺
From: https://www.cnblogs.com/2020fengziyang/p/17629700.html