[USACO 2018 Ope G]Talent Show

NC24279. [USACO 2018 Ope G]Talent Show

描述

Farmer John要带着他的N头奶牛，方便起见编号为1…N，到农业展览会上去，参加每年的达牛秀！他的第ii头奶牛重量为wi，才艺水平为ti，两者都是整数。

在到达时，Farmer John就被今年达牛秀的新规则吓到了：

（一）参加比赛的一组奶牛必须总重量至少为W（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且

（二）总才艺值与总重量的比值最大的一组获得胜利。

FJ注意到他的所有奶牛的总重量不小于W，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

输入描述

输入的第一行包含N（1≤N≤250）和W（1≤W≤1000）。下面N行，每行用两个整数wi（）和titi（1≤ti≤1000）描述了一头奶牛。

输出描述

请求出Farmer用一组总重量最少为W的奶牛最大可能达到的总才艺值与总重量的比值。如果你的答案是AA，输出1000A向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

示例1

输入:

输出:

说明:

在这个例子中，总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为11、重量为10的奶牛，但是由于我们需要至少15单位的重量，最优解最终为使用这头奶牛加上才艺值为21、重量为20的奶牛。这样的话才艺与重量的比值为(11+21)/(10+20) = 32/30 = 1.0666666...，乘以1000向下取整之后得到1066。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 44ms, 内存消耗: 1368K, 提交时间: 2019-07-05 12:31:18

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
double dp[100005];int w[255],v[255];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=0;i<100001;i++) dp[i]=1e9; 
	dp[0]=0;
	for(int i=0;i<n;i++){
		for(int j=100001;j>=v[i];j--){
			dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	double ans=0;
	for(int j=0;j<=100001;j++){
		if(dp[j]>=m)
		ans=max(ans,(double)j/dp[j]);
	}
	cout<<(int)(ans*1000);
}

上一题

下一题

详情