ACM最大比率问题:有N道题目,每道题目有不同的分值和难度,分别为Ai,Bi。 20

要求从某一题开始连续选至少K道题目,满足分值和与难度和的比最大。例:N=7,K=3A4398992B2211211选择第3题到第6题,比为(9+8+9+9)/(1+1+2... 要求从某一题开始连续选至少K道题目,满足分值和与难度和的比最大。
例:N=7,K=3
A 4 3 9 8 9 9 2
B 2 2 1 1 2 1 1
选择第3题到第6题,比为(9+8+9+9)/(1+1+2+1)=7
这是上例最优解
展开
 我来答
匿名用户
2011-05-20
展开全部
O(n^2)直接枚举就好了,数据范围大的话可以分数规划做到O(nlgn),二分答案ans以后构造数列
C[] = A[] - B[] * ans ,然后O(n)时间做一次最大连续子段和即可
htt5156
2011-05-20 · 超过22用户采纳过TA的回答
知道答主
回答量:78
采纳率:0%
帮助的人:60.6万
展开全部
dp
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
j550366043
2011-05-21
知道答主
回答量:21
采纳率:0%
帮助的人:15.2万
展开全部
兄弟,你作业阿 我也要这题阿 ...
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 更多回答(1)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式