关注
由于同时和a[j]和j有关所以不能单纯维护当作斜率相关的问题来做
本问题是经典的决策单调性问题。
考虑我们选择j时如果j1>j2且a[j1]>a[j2]显然j2时候不如j1,因此我们用单调队列筛掉这些不符合条件的j2,最后得到一个单调下降子序列。
同理,选择i时如果i1<i2且a[i1]>a[i2]显然i2时候不如i1,帅选后i的选择区域也将在一个单调上升子序列中。
现在在一个单调上升子序列中选择i,一个单调下降子序列中选择j。
接下来考虑j对i1和i2的值f(i1,j)=(A[i1]+A[j])*(j-i1),f(i2,j)=(A[i2]+A[j])*(j-i2)作差
不妨设i1>i2
f(i1,j)-f(i2,j)=j*(A[i1]-A[i2])-(A[i1]*i1-A[i2]*i2)-A[j]*(i1-i2)
=(A[i1]-A[i2],i1-i2)·(j,-a[j])-(A[i1]*i1-A[i2]*i2)
显然,随着j的增大f(i1,j)-f(i2,j)单调递增,也就是说,对于任意i1,i2存在一个在j0之后
(f(i1,j)-f(i2,j))*(j-j0)>=0
故我们在i待选择的单调上升子序列中的每个相邻元素计算其分界的j即可。具体实现就是用一个单调栈维护每个分界点,每次对相邻两个元素二分其分界点,然后维护单调栈。
1.得到i的候选序列I={i1,i2...ip}
2.得到j的候选序列J={j1,j2...jq}
3.初始单调栈s为空
4.枚举x,根据f(ix,j)-f(ix+1,j)的算出分界点jx,将jx比栈顶元素小,不断把元素踢出,然后加入jx
5.根据单调栈中的元素,得到每个序列J最优的决策ix,计算,并求最大值。
PS:这个问题转化称这样可能更好理解,二维的点集A={(i,a[i])},B={(i,-a[i])},在A中取一个点,在B中取一个点,最后要求其面积最大,当然最后做法本质没区别
查看原帖
3 2
相关推荐
牛客热帖
更多
正在热议
更多
# 春招什么时候投? #
7256次浏览 116人参与
# 牛友的春节生活 #
3877次浏览 109人参与
# 春节前,你还在投简历吗? #
10022次浏览 132人参与
# 从夯到拉,锐评职场mentor #
2735次浏览 55人参与
# 牛客AI体验站 #
14023次浏览 261人参与
# 实习到现在,你最困惑的一个问题 #
2895次浏览 95人参与
# 春节提前走,你用什么理由请假? #
6488次浏览 167人参与
# 备战春招/暑实,现在应该做什么? #
2646次浏览 98人参与
# 距离春招还有一个月,你现在是什么开局? #
4254次浏览 92人参与
# 聊聊Agent开发 #
19289次浏览 511人参与
# 暑期实习什么时候投? #
4951次浏览 128人参与
# 推荐一个值得做的AI项目 #
5253次浏览 153人参与
# 听劝,这个简历怎么改 #
380640次浏览 1826人参与
# 机械人的秋招小目标 #
28342次浏览 239人参与
# 我的AI电子员工 #
27627次浏览 186人参与
# 腾讯工作体验 #
568181次浏览 3712人参与
# 参加完秋招的机械人,还参加春招吗? #
108240次浏览 704人参与
# 实习的内耗时刻 #
221504次浏览 1643人参与
# 互联网公司评价 #
488453次浏览 4119人参与
# bilibili求职进展汇总 #
180880次浏览 1074人参与
查看10道真题和解析
凡岛公司福利 737人发布