bzoj 5281 [Usaco2018 Open]Talent Show——0/1分数规划
2024-08-25 14:31:53
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=5281
把分子乘1000,就能在整数里做了。
这种水题也花了这么久……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int N=,M=;
int n,lm,v[N],c[N],l,r,mid,ans;
ll a[N],dp[M];
bool check()
{
for(int i=;i<=n;i++)
a[i]=c[i]-(ll)mid*v[i]; memset(dp,-,sizeof dp);
dp[]=; for(int i=;i<=n;i++)
for(int j=lm;j>=;j--)
dp[min(lm,j+v[i])]=
max(dp[min(lm,j+v[i])],dp[j]+a[i]); return dp[lm]>=;
}
int main()
{
scanf("%d%d",&n,&lm);
for(int i=;i<=n;i++)
{
scanf("%d%d",&v[i],&c[i]);
c[i]*=; r+=c[i];
} while(l<=r)
{
mid=l+r>>;
if(check())ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
return ;
}
最新文章
- EF架构~EF异步改造之路~仓储接口的改造~续
- Jquery 基本知识(二)
- kuangbin_MST C (POJ 2031)
- android之打开网页
- Wget命令
- listview当选中某一个item时设置背景色其他的不变
- 2015南阳CCPC L - Huatuo&#39;s Medicine 水题
- linux 安装GCC
- 【转】学习Flex ActionScript 3.0 强烈推荐电子书
- [Ext JS 4] 实战Chart 协调控制(单一的坐标,两个坐标)
- C# 获取磁盘容量
- python 分支语句 循环语句
- PAT1052:Linked List Sorting
- C++ 浅拷贝与深拷贝探究
- [Sw] 使用 Swoole Server task/协程 处理大数据量异步任务时注意
- CSS3中很容易混淆的transform,translate,transition。如何去区分,以及综合写法。
- 变量,id()
- (转)final修饰基本类型和引用类型变量的区别
- nginx限制ip访问(转)
- 14.linux下复制粘贴