洛谷 P4377 [USACO18OPEN]Talent Show + 分数规划
2024-10-21 14:44:49
分数规划
分数规划可以用来处理有关分数即比值的有关问题。
而分数规划一般不单独设题,而是用来和dp,图论,网络流等算法结合在一起。
而基础的做法一般是通过二分。
二分题目我们都知道,需要求什么的最小或最大值,就二分什么。
而该最小或最大值都会满足单调性。
设当前最大值为\(maxn\),如果存在比值使得比\(maxn\)大,则有\(y/x>maxn\),化简得:\(y-x*maxn>0\)
就可以更新答案。所以满足二分性(即\(maxn\)越大则\(y-maxn*x\))越小则越难更新答案。
而二分check可以通过排序求得\(y[i]-x[i]*maxn\)的最大值,然后直接贪心取最大值,最后判断是否大于0即可
该题目
而对于该题来说,贪心的话显然不能通过排序求最大值,因为还有一个重量限制,所以可以用背包。
重量即为原数据的重量,价值即为\(y[i]-x[i]*maxn\),在转移时需要把所有重量大于W的最后都转移到W上
最后方便统计。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, dp[100100];
struct dat {
int w, t;
int bizhi;
}data[1001000];
bool check(int mid)
{
memset(dp, 128, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= n; i++)
data[i].bizhi = data[i].t - mid * data[i].w;
int ha = dp[m];
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
if (dp[j] != ha)
dp[min(m, j + data[i].w)] = max(dp[min(m, j + data[i].w)], dp[j] + data[i].bizhi);//取min的意义是为了让所有质量都大于m的都转移到一个地方
if (dp[m] >= 0) return 1;//如果存在一个价值使得能够>=0即满足条件,则该mid可以,寻找更大的
else return 0;
}
signed main()
{
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &data[i].w, &data[i].t), data[i].t *= 1000;
int l = 0, r = 150000, ans;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
printf("%lld", ans);
return 0;
}
最新文章
- PostSharp 4.0注册机实现过程
- ubuntu和windows上pip和windows上conda国内源更新module
- BIT LA 4329 Ping pong
- 函数内部的函数中的this都是指向window
- Dom新find
- BZOJ 3998 [TJOI 2015] 弦论 解题报告
- POJ 1195 Mobile phones (二维树状数组或线段树)
- autolisp 列表 resbuf
- 温故知新-------jQuery层次选择器
- CentOs Linux 文件位置标记
- python multiprocessing.Process
- c# 判断datatable中是否存在某列
- BIP Requests Are Failing With Error ";OPP Error Oracle.apps.xdo.XDOException: Error Creating Lock Fil
- asp.net core系列 44 Web应用 布局
- 20190325-HTML框架、audio标签、vedio标签、source标签、HTML表单
- SQL-51 查找字符串&#39;10,A,B&#39; 中逗号&#39;,&#39;出现的次数cnt。
- Linux CentOS7下安装Python3及其setuptools、pip
- Java--- Ambiguous mapping. Cannot map ";***Controller"; been method解决办法
- ruby 基础知识 - Class 与 Module
- 电子产品使用感受之--Mac Mini 买了之后有什么用?-- 开发啊!
热门文章
- ②将SVN迁移到GitLab-多分支多标签迁移
- Python接口自动化基础---环境准备
- 【开发笔记】- Java读取properties文件的五种方式
- python day 8: re模块补充,导入模块,hashlib模块,字符串格式化,模块知识拾遗,requests模块初识
- npm 安装 react-devtools
- Vivado中备份设计好的block design
- python之变量的数据类型(1)int 、bool 、str 及for循环运用
- CentOS7.x安装Java
- linux系统多网卡热备实现高并发负载均衡
- Linux系统下RAID5和RAID10的磁盘阵列配置