这个题目转化为以下问题是关键:
1. X[i] * P1 + Y[i] * P2 <= cookies[i] (For every i).
2. S = X[0] + X[1] + ... X[n-1] = Y[0] + Y[1] + ... Y[n-1]
3. .X[i] + Y[i] <= S (For every i)
这个其实很显然,而且S具有单调性,为二分做准备。
但是如果一开始就直接陷入高复杂度的dp中,而忽视了这个简单的单调性就比较悲剧。
二分判断d[S][S] 是否可以达到,这样的dp一般可以转化为d[N]最大可以跟什么数搭配,于是二维的状态降了一维。
const int N = 1005;
int d[N], a[N], n;
int g[N];
bool ok(int s, int p1, int p2) {
int i, j, k, t;
memset(d, -1, sizeof(d));
d[0] = 0;
for (i = 0; i < n; ++i) {
memset(g, -1, sizeof(g));
for (j = 0; j * p1 <= a[i]; ++j) {
k = (a[i] - j * p1) / p2;
k -= max(j + k - s, 0);
if (k < 0) continue;
for (t = s; t >= j; --t) {
if (d[t - j] == -1) continue;
g[t] = max(g[t], d[t - j] + k);
}
}
for (j = 0; j <= s; ++j) {
d[j] = g[j];
}
}
return d[s] >= s;
}
class ColorfulCookie {
public:
int getMaximum(vector <int> a, int P1, int P2) {
int i, j, k, t;
n = a.size();
for (i = 0; i < n; ++i) {
::a[i] = a[i];
}
int l = 0, r = 1000;
while (l <= r) {
int mid = (l + r) >> 1;
if (ok(mid, P1, P2)) l = mid + 1;
else r = mid - 1;
}
return r * (P1 + P2);
}
};
分享到:
相关推荐
NVIDIA 15.0 vGPU显卡驱动,适用于版本VMware esxi 8.0,支持RTX6000/RTX8000/M60/A10/A16/A40等显卡。版本号:NVIDIA-GRID-vSphere-8.0-525.60.12-525.60.13-527.41
rem rem $Header: summit2.sql 27-jun-2000.12:30:22 slari Exp $ rem ... All rights reserved. rem rem NAME rem summit2.sql - rem DESCRIPTION rem rem RETURNS ...rem Create and populate tables and sequences to...
资源简介 第1章 数据结构. 1 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 范例1-2 一维数组应用 3 ...2.1.6 求反正切 ...
第1章 数据结构. 1 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 范例1-2 一维数组应用 3 1.1.3 一维数组的高级应用 5 ...
配书光盘Readme文件 C 语言通用范例开发金典 第1章 数据结构. 1 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 ...2.1.2 求浮点数的...
步进工作过程 1、步进电机带动加工台面在左限位开关X0和右限位... 3、步进电机在减速时同样是没有减速时间,立刻减速到1000HZ,如此方式并不适合实际应用; 4、操作停止按钮时,步进电机不减速停止,会造成机械损伤。
<!...--STATUS OK--><html><head>;..._position:;min-height:100%}#head{padding-bottom:100px;text-align:center;*z-index:1}#ftCon{height:100px;position:absolute;bottom:44px;text-align:center;...
Writing Code with the ADO.NET Data Services Client Library 528 Summary 533 Part 5 Building Desktop User Interfaces 534 24 Taking Console Applications to the Limit 536 Introducing the Password...
本文应用RT-PCR和RACE方法扩增出三角揭指藻二酰基甘油转移酶(Ptdgat)全长 cDNA,其完整编码框(ORF))为1587 bp,编码528个氨基酸.基于克隆所得Ptdgat的ORF构建了反向互补RNA干扰载体,并用基因枪PDS-1000/He转化野生型...
该系统数据传输总速率可高达528MB/s,实时流盘速度可达150MB/s,存储容量可扩展至1000GB以上。 关键词:FPGA 超高速 实时 数据采集 数据存储 在超高速数据采集方面,FPGA(现场可编程门阵列)有着单片机和...
经典中的经典! 目 录 译者序 序 前言 第一部分 快速开发的基础 第1章 Delphi 5下的Windows编程 1 1.1 Delphi产品家族 1 1.2 Delphi是什么 3 1.2.1 可视化开发环境 3 1.2.2 编译器的速度和已编译代码的效 ...
The C++ Standard Library A Tutorial and Reference (2nd Edition)+cppstdlib-code.zip C++标准库(第二版)英文版.pdf 非扫描版+源代码 Prefaceto the SecondEdition xxiii Acknowledgments for the Second...
C#编程经验技巧宝典源代码,目录如下: 第1章 开发环境 1 <br>1.1 Visual Studio开发环境安装与配置 2 <br>0001 安装Visual Studio 2005开发环境须知 2 <br>0002 配置合适的Visual Studio 2005...
15.2.4 添加事件 528 15.2.5 公开内部Web控件 530 15.3 动态加载用户控件 531 15.4 局部页面缓存 534 15.4.1 VaryByControl 535 15.4.2 共享缓存控件 536 15.5 总结 537 第16章 主题和母版页 538 ...