很显然是个DP
有方程f[i]=max{f[j]+Ax^2+Bx+C} x=s[i]-s[j] j∈[1,i-1]
这样一个DP方程是O(n^2)的,对于原题最多只能过50%数据
那么这道题可以斜率优化
从方程着手,方程可以化为
f[i]=max{(f[j]+A*s[j]^2+B*s[j]+C)+(-2A*s[i]*s[j])}+A*s[i]^2+A*s[i]
我们把(f[j]+A*s[j]^2+B*s[j]+C)看成y,(-2A*s[i]*s[j])看成-kx,-s[i]是斜率,递减,-2A*s[j]是x,递增
那么每个决策对应平面上一个点
而且斜率和横坐标均单调,可以用单调队列维护
对于每个i
弹出单调队列队首直到单调队列队首最优,
计算f[i]
在单调队列中维护相邻两个决策点的斜率单调递减
push决策点i
代码写得比较丑……
分享到:
相关推荐
APIO2021课件
CCF全国青少年信息学奥赛 APIO 亚洲与太平洋地区信息学奥林匹克 2012年 试题 中文版
APIO2008 亚太地区信息学奥林匹克竞赛
apio(亚洲与太平洋地区信息学奥林匹克(Asia-Pacific Informatics Olympiad, APIO),是一个面向亚太地区在校中学生的信息学科竞赛。) 2010 年的测试数据 atm一题 供下载测试用
APIO2016课件,包含有位运算最小生成树以及组合数取模
2014年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版
apio2009 convention 试题分析
APIO2015 数据 题面自己搜,1.巴厘岛的雕塑 N个数,分成连续的A-B个组,让每个组的和或起来最小,求最小值。 对于Task1 n 由于涉及到位运算,所以很容易想到按二进制位来做。要让答案最小,显然要从二进制高位...
2007年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版
APIO2012_網絡流題選講。 网络流题选讲 清华大学 计03 李宇亮
2015年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版
APIO2018的题面与部分课件与pdf和ppt,.在此分享一下。
题目大意 在一个数轴上: 给定 N 个商店,每个商店有一个开业时间、关门时间、坐标和销售物品的种类 同时有 M 个询问,每个询问给你一个时间 t[i] 和地点 d[i],试求在 t[i] 时刻,一个住在 d[i] 的人,为了买某种...
讲题: beads.pdf palindrome-pres.pdf sequence.pdf 课件: 冯齐纬 彭天翼 毕克 罗雨屏 胡渊鸣 陈立杰
1钱桥_提交答案题目的处理方法.pptx 2冯齐纬_URAL题目选讲 3曹钦翔_线段树应用.pptx 4李超_Problems in UralChampionship.pptx 5陈许旻_数论与AI
2014年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题测试数据
APIO2015的problemset, 非常的清楚.
用于开放FPGA板的开源生态系统Apio(发音为[ˈa.pjo])是一个多平台工具箱,具有静态的预构建软件包,项目配置工具和简单的命令界面,可用于验证,综合,模拟和上传Verilog设计。 Icestudio使用 。目录安装安装和 ...
2008年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版
2014年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版